Magic labeling on graphs with ascending subgraph decomposition

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 H 1 ,H 2 , … ,H t without isolated vertices such that H i is isomorphic to a proper subgraph of H i +1 for 1 ≤ i ≤ t - 1 , where { E ( H 1 ) , … ,E ( H t ) } 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 H i (1 ≤ i ≤ n ) is w ( H i ) = ∑ v ∈ V ( H i ) f ( v ) + ∑ e ∈ E ( H i ) f ( e ) . If the weight of each ascending subgraph is constant, say w ( H i ) = 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.