login/create account
Graceful Tree Conjecture
Conjecture All trees are graceful
Label the vertices of a simple undirected graph 
(where 
and 
) with integers from 
to 
. Now label each edge with absolute difference of the labels of its incident vertices. The labeling is said to be graceful if the edges are labelled 
through inclusive (with no number repeated).
A graph is called graceful if it has at least one such labeling. This labeling was originally introduced in 1967 by Rosa. The name graceful labeling was coined later by Golomb.
Gracefully labeled graphs serve as models in a wide range of applications including coding theory and communication network addressing.
The graceful labeling problem is to determine which graphs are graceful. It is conjectured (by Kotzig, Ringel and Rosa) that all trees are graceful.
Despite numerous (more than 200) publications on graceful labeling for over three decades, only a very restricted classes of trees (and also of some other graphs) have been shown to be graceful. These restricted classes include paths, stars, complete bipartite graphs, prism graphs, wheel graphs, caterpillar graphs, olive trees, and symmetrical trees.
Bibliography
* indicates original appearance(s) of problem.
Graceful Tree examples
On September 29th, 2014 Anonymous says:
If you want to develop intuition for a proof, feel free to use this program I wrote (http://bl.ocks.org/NPashaP/7683252). Good luck.
applications of graceful graphs
On November 30th, 2009 Anonymous says:
can you explain some applications of graceful graphs
Apllication of graceful labeling
On June 12th, 2010 Anonymous says:
I want the application of graceful label
graph theory
On November 30th, 2009 Anonymous says:
Can you pls send some applications of gracefulgraphs
Tentative proof
On May 5th, 2009 Anonymous says:
I just saw this paper on arxiv, entitled "A complete proof of The Graceful Tree Conjecture using the concept of Edge Degree".
I'm surprised to see such a short proof for such a long-standing open problem, but surely people who are a lot more into the subject than I will be able to provide more constructive comments on the paper.
Re: Tentative proof
On May 6th, 2009 Robert Samal says:
It's a bit worrisome that this is already the eight version on the arXiv ... this probably means that the previous seven versions had some sort of flaw in it ... I haven't read the paper though ...
injective labeling
On April 14th, 2009 Anonymous says:
Rosa (1967) required the labeling to be injective.
not a problem
On August 2nd, 2007 Anonymous says:
graceful labellings are defined for arbitrary graphs, not just trees.
Re: wording
On August 4th, 2007 rs says:
Truly, this was unfortunate choice of wording; I corrected it. (Btw to provide a graceful labeling for complete bipartite graphs is quite an easy exercise.)
graceful labeling of complete bipartite graphs
On April 12th, 2008 Anonymous says:
how to give a graceful labeling to complete bipartite graph. Can u suggest some efficient algorithm or scheme for that Plz email it to [email protected] if u have any...
thanx
Drupal
CSI of Charles University
Bibliography
Many, many references on the topic appear in Joseph Gallian's "A Dynamic Survey of Graph Labeling", section 2 ( https://www.combinatorics.org/ds6 ).