Vertex-magic labeling of trees and forests

MacDougall, James A. and Gray, I. D. and Wallis, W. D. and McSorley, J. P. (2003) Vertex-magic labeling of trees and forests. Discete Mathematics, 261 . pp. 285-298.

 Preview
PDF - Accepted Version
A {\em vertex-magic total labeling} of a graph $G(V, E)$ is a one-to-one map $\lambda$ from $E \cup V$ onto the integers $\{1, 2, . . . , \mid E\mid + \mid V\mid\}$ such that $$\lambda(x) +\Sigma\lambda(xy),$$ where the sum is over all vertices $y$ adjacent to $x$, is a constant, independent of the choice of vertex $x$. In this paper we examine the existence of vertex-magic total labelings of trees and forests. The situation is quite different from the conjectured behavior of {\em edge}-magic total labelings of these graphs. We pay special attention to the case of so-called {\em galaxies}, forests in which every component tree is a star.