Magic labeling on graphs with ascending subgraph decomposition

Abstract

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₁,H₂,…,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₁),…,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 (Hi)f(v) + ∑ _e∈E(Hi)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.