Magic labeling on graphs with ascending subgraph decomposition - Pancahayani, Sigit; Simanjuntak, Rinovia; Uttunggadewa, Saladin (Electronic Journal of Graph Theory and Applications (EJGTA), 2024)
Let t and q be positive integers that satisfy C(t + 1,2) ≤ q < C(t + 2,2) and let G be a simple and finite graph of size q. G is said to have ascending subgraph decomposition (ASD) if G can be decomposed into t subgraphs H1,H2,…,Ht without isolated vertices such that Hi is isomorphic to a proper subgraph of Hi+1 for 1 ≤ i ≤ t - 1, where {E(H1),…,E(Ht)} is a partition of E(G). A graph that admits an ascending subgraph decomposition is called an ASD graph.In this paper, we introduce a new type of magic labeling based on the notion of ASD. Let G be an ASD graph and f : V (G) ∪E(G) →{1,2,…,|V (G)| + |E(G)|} be a bijection. The weight of a subgraph Hi (1 ≤ i ≤ n) is w(Hi) = ∑ v∈V (Hi)f(v) + ∑ e∈E(Hi)f(e). If the weight of each ascending subgraph is constant, say w(Hi) = k, ∀ 1 ≤ i ≤ t, then f is called an ASD-magic labeling of G and G is called an ASD-magic graph. We present general properties of ASD-magic graphs and characterize certain classes of them.