Graceful Tree Conjecture

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 G(V,E) (where |V|=n and |E|=m) with integers from 0 to m. 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 1 through m 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 T is a fixed tree with m edges, then complete graph on 2m+1 vertices decomposes into 2m+1 copies of T.

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 graphs are graceful. This is also an open problem. Some special cases of lobsters (eg : lobsters with perfect matching) are proved graceful [Morgan’02].
  • Complexity of graceful labeling is open. A related problem called harmonious labeling was shown to be NP-complete.
  • Improve approximate factors of 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