Towards the Graceful Tree Conjecture: A Survey
Mousa Alfalayleh, Ljiljana Branković, Helen Giggins, Md Zahidul Islam · 2004
A graceful labelling of an undirected graph G with n edges is a one-to-one function from the set of vertices of G to the set {0, 1, 2,..., n} such that the induced edge labels are all distinct. An induced edge label is the absolute value of the difference between the two end-vertex labels. The Graceful Tree Conjecture states that all trees have a graceful labelling. In this survey we present known results towards proving the Graceful Tree Conjecture. 1 Introduction. A graceful labelling of an undirected graph G with n edges is a one-to-one function from the set of vertices of G to the set {0, 1, 2,..., n} such that the induced edge labels are all distinct. An induced edge label is the absolute value of the difference between the two endvertex labels. This labelling was originally introduced in 1967 by Rosa who also showed