Supermagic graphs with many different degrees

Let G = (V,E) be a graph with n vertices and e edges. A supermagic labeling of G is a bijection f from the set of edges E to a set of consecutive integers {a, a + 1, . . . , a + e − 1} such that for every vertex v ∈ V the sum of labels of all adjacent edges equals the same constant k. This k is called a magic constant of f , and G is a supermagic graph. The existence of supermagic labeling for certain classes of graphs has been the scope of many papers. For a comprehensive overview see Gallian’s Dynamic survey of graph labeling in the Electronic Journal of Combinatorics. So far, regular or almost regular graphs have been studied. This is natural, since the same magic constant has to be achieved both at vertices of high degree as well as at vertices of low degree, while the labels are distinct consecutive integers. The question of the existence of highly irregular supermagic graphs had remained open. In this paper we give a positive answer: the degree difference of a supermagic graph can be arbitrarily high. Moreover, we show that the composition G[Kn] is supermagic for every supermagic graph G and odd n.