Graceful Tree Conjecture (GTC) is one of my favorite open problems. I posted it on Open Problem Garden couple of years back. I enjoy reading papers related to graceful labeling and try to keep as up-to-date as possible with the progress towards GTC. Here is a brief introduction to GTC.

Graceful Labeling :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 labeled 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 [Rosa'67]. The name graceful labeling was coined later by Golomb. It is easy to see that stars and paths are graceful. Some known graceful graphs are paths, stars, complete bipartite graphs, prism graphs, wheel graphs, caterpillar graphs, olive trees, and symmetrical trees, gear graphs, rectangular grids.

Gracefully labeled graphs have applications in coding theory and communication network addressing. Look at this paper [Basak'04] for an application in MPLS Multicasting. The following conjecture is due to Kotzig, Ringel and Rosa.

Graceful Tree Conjecture (GTC): All trees are graceful.

Ringel’s Conjecture :If is a fixed tree with edges, then complete graph on vertices decomposes into copies of .

Exercise :The existence of a graceful labeling of a given graph G with n edges is a sufficient condition for the existence of a cyclic decomposition of a complete graph of order 2n+1 into subgraphs isomorphic to G. In particular, GTC implies Ringel’s conjecture.

A **caterpillar** graph is a tree such that if all leaves and their incident edges are removed, the remainder of the graph forms a path. Here’s a cute exercise. There is an elegant inductive proof.

Exercise :Prove that all caterpillar graphs are graceful.

Open Problems :

- Graceful Tree Conjecture (GTC)
is still open. There are couple of papers on arxiv claiming to have settled GTC. I went through the proofs and found some mistakes.- As an intermediate problem, prove that all
lobster graphsare graceful. This is also an open problem. Some special cases of lobsters (eg : lobsters with perfect matching) are proved graceful [Morgan'02].Complexityof graceful labeling is open. A related problem called harmonious labeling was shown to be NP-complete.- Improve
approximate factorsof relaxed graceful labeling [Bussel'02].

**References :**

**[Rosa'67]**Alex Rosa,**On certain valuations of the vertices of a graph.***Theory of Graphs*, (1967) 349–355**[Bussel'02]**Frank Van Bussel:**Relaxed Graceful Labellings of Trees.***Electr. J. Comb.*9(1): (2002)**[Morgan'02]**David Morgan:**All Lobsters with Perfect Matchings are Graceful.***Electronic Notes in Discrete Mathematics*11: 503-508 (2002)**[Basak'04]**Ayhan Basak,**MPLS Multicasting Using Caterpillars and a Graceful Labelling Scheme**,*Eighth International Conference on Information Visualisation*(IV’04), pp.382-387, 2004

I will make a few comments on the Graceful Tree Conjecture.

Original reference for [Basak'04] is “I. C. Arkut, R.C. Arkut, A. Basak, “Topology Constrained Label Switching for Multicast Routing,” iscc, pp.453, Eighth IEEE Symposium on Computers and Communications, 2003″ (http://doi.ieeecomputersociety.org/10.1109/ISCC.2003.1214160)

Note I. C. Arkut same person as I. Cahit.

Complexity of graceful labeling is not known but for weaker version of graceful and harmonious labeling known as cordial labeling has been shown to be NP-complete. Therefore probably it is NP-complete for general graphs. But it is difficult to say the same for graceful trees. I have proposed a problem on the complexity of graceful trees in another group. See

http://www.facebook.com/topic.php?uid=2209984937&topic=9225&ref=mf

Cahit

Thanks for the references and details about NP-completeness.

The best possible range-relaxed labeling for general graphs (as a function of the graph size) is O(|E|^4/3), which I believe is due to Bollobas and someone else. (|E|^3/2 is easy by induction. I suspect it may be possible to improve the inductive argument to the best possible by an amplification trick, but I don’t know for a fact.)

None of the basic methods seem to improve on Bussel’s 2|E| for trees, although I suspect that it’d be doable (maybe even to 1 + \epsilon) if someone more qualified than myself worked on it :).

Sorry if I’m over-concentrating on this one subject — I did a research project on it in high school and like to think I know a little about it.

Thanks for the insights

can you send some applications of graceful graphs

You can find a nice way to find almost graceful labelings of trees here: http://sites.google.com/site/almostgraceful/home

I read all over the Internet that graceful graphs have applications in network addressing problems, but I have not found a single example of this. Can you provide some examples of network addressing related to graceful graphs?

Look at this paper : MPLS multicasting using caterpillars and a graceful labelling scheme.

Pingback: Graceful Labeling of Caterpillar Graphs | TrueShelf

Pingback: Recreational Math Books – Part I « My Brain is Open

A possible breakthrough has been found for the algorithmic proof of the graceful tree conjecture. At this time see

http://www.academia.edu/2065705/_Proof_Plan_Graceful_Tree_Conjecture

Tentative title of my (forthcoming) paper is:

“Algorithmic Proof of the Ringel-Kotzig Tree Packing Conjecture”.

I. Cahit

Pingback: Graceful Diameter-6 Trees | My Brain is Open

“Label the vertices of a simple undirected graph … with integers from to 1 to m.”

Should it be “integers from 1 to n”?

The integers are from 0 to m.

Pingback: Open problems for 2014 | My Brain is Open