Status of Graceful Tree Conjecture in 1989
Ibrahim Cahit · 1990
The root of graph labellings go back to a problem stated by Gerhard Ringel. Let T be a given tree with n vertices; then the edges of K 2n−1 can be partitioned into (2n−1) trees isomorphic to T [1]. A.Rosa in his well-known 1966 paper mentioned stronger version of this conjecture which was attributed to A. Kotzig. Let T be a given tree with n vertices, then the edges of K 2n−1 can be partitioned cyclically into (2n−1) trees isomorphic to T [2]. Rosa was first to give the connections of these conjectures with certain valuations (labellings) of the vertices of a tree [2] but the name “graceful” was coined by Golomb [3] which popularizes the β -labelling (in terms of Rosa’s terminolgy) problem of trees. As today well over 100 papers have appeared in the literature around these conjectures but none of them have triggered any single hope towards its resolution (e.g., see surveys [4], [5], [10]). These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.