by

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

17 thoughts on “Graceful Tree Conjecture”

  1. 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

    Reply

  2. 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.

    Reply

  4. 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?

    Reply

  5. Pingback: Graceful Labeling of Caterpillar Graphs | TrueShelf

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

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

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

    Should it be “integers from 1 to n”?

    Reply

  10. Pingback: Open problems for 2014 | My Brain is Open

  11. Hello! I am conducting a thesis paper about graceful labeling, and this page has been a great help to me. I also searched the internet for articles or PDF’s on practical uses of Graceful labeling. All I could found was about radio astronomy, circuit design, and X-ray crystallography, but I failed to find specific examples for this matter. Can you provide some examples on these fields? I would be very grateful if you could.

    Reply

  12. This path, your personal pc or pc system will keep on being value-free
    of viruses, and oneself won’t comprise in direction of strain any longer as regards to squandering
    documents, at minimal, because of in the path of viruses https://math-problem-solver.com/ .
    The sizes of the faces might differ or may be similar.

    Reply

Leave a comment