Vertex-magic total labelings of graphs

Abstract

A vertex-magic total labeling of a graph with v vertices and e edges is defined as a one-to-one map taking the vertices and edges onto the integers 1, 2,..., v + e with the property that the sum of the label on a vertex and the labels on its incident edges is a constant independent of the choice of vertex. Properties of these labelings are studied. It is shown how to construct labelings for several families of graphs, including cycles, paths, complete graphs of odd order and the complete bipartite graph K_n,n. It is also shown that labelings are impossible for some other classes of graphs.