Graceful Tree Conjecture for Infinite Trees

A graceful labeling of a graph G with n edges is an injective function from the set of vertices of G to the set {0, 1, 2,..., n} such that the edge labels, the absolute difference between the two endvertex labels, are all distinct. One of the most fa-mous open problems in graph theory is the Graceful Tree Conjecture which states that every finite tree has a graceful labeling. Despite forty years of research effort, little progress has been made towards resolving this conjecture. Today, some of the known graceful trees are caterpillars, trees with at most 4 endvertices, trees with diameter at most 5, and trees with at most 27 vertices. In this paper, we considered the infinite version of the Graceful Tree Conjecture. First, the notions of bijective graceful N-labeling and bijective graceful N/N-labeling of infinite graphs were introduced. Such labelings were then shown to be possible for infinite graphs built by certain types of graph amalgamations. Finally, based on the tools developed, we were able to characterize all the infinite trees that have a bijective graceful N/N-labeling and hence solved the Graceful Tree Conjecture for infinite trees. the electronic journal of combinatorics 13 (2006), #R00 1