Graceful Diameter-6 Trees

Graceful Tree Conjecture is one of my favorite open problems (See this earlier post). Trees with diameter 4 and 5 are known to be graceful a decade ago.

One of my advisees, Matt Superdock, made progress towards proving that all diameter 6 trees are graceful. Matt is an undergraduate senior in our Mathematics Department. He proved that an interesting class of diameter 6 trees are graceful. His thesis is available here.

I hope his work motivates more researchers to make progress towards resolving Graceful Tree Conjecture, particularly for diameter 6 trees. Matt’s work really tests the limit of current techniques. Perhaps we need new techniques/insights to prove that all diameter 6 trees are graceful.




3 thoughts on “Graceful Diameter-6 Trees

  1. Quick Response:

    Matt Superdock!s thesis entitled “The Graceful Tree Conjecture: A Class of Graceful Diameter-6 Trees” is a serious attempt to settle the gracefulness of trees of diameter 6 as (Kintali indicated) Matt’s work really tests the limit of current techniques. This statement is not complete.

    I have started to read the thesis from backward. The list of references has an important missing paper from the point of “diameter” of graceful trees. Namely

    I. Cahit, ” Status of Graceful Tree Conjecture in 1989″, in Topics in Combinatorics and Graph Theory (Essays in Honour of Gerhard Ringel), eds. R. Bodendiek, R. Henn, Physica-Verlag Heidelberg, 1990, pp.175-184.

    In this paper I have introduced assignment of canonical (spiral) labeling for the complete trees (radial trees in the thesis) of diameter k (k>3). The labeling is quite different than the Hraciar and Haviar’s method of transfers. The conjectures 6.1 and 6.2 listed in page 80 may be handled by the spiral graceful labeling technique. You can find further results on this method in my presentation at

    • @Cahit, Thanks for pointing out your paper. I will go through it and see if we missed any known techniques.

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

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s