Magic labeling on graphs with ascending subgraph decomposition.

Let t and q be positive integers that satisfy t+1 2 = q < 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) = P vV (Hi) f(v) + P eE(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. [ABSTRACT FROM AUTHOR]