Control Systems and Computers

DOI: https://doi.org/10.15407/usim.2016.01.016

Upr. sist. maš., 2016, Issue 1 (261), pp. 16-25, 33.

UDC 519.17

Dmytro A. Petreniuk, PhD of Physical and Mathematical Sciences, Senior Science Researcher, Glushkov Institute of Cybernetics of NAS of Ukraine, Kyiv, Glushkov ave., 40, Kyiv, 03187, E-mail: quitar-player@meta.ua 

Graceful Trees: the State of Arts and the Prospects

Graceful Tree Conjecture is one of the most popular math conjectures. It was formulated almost half a century ago, but even today it is still far from being completely solved. A. Krishnaa in 2004 and J. Gilbert in 2009 proposed their proofs of the Conjecture, but they turned out to be wrong or incomplete. The article contains a brief review of the state of art in solving the Conjecture, including some results that have been proposed by the author.

Graceful labeling of undirected graph G with n edges is an injection from vertex set of graph G to {0, 1, 2, …, n} such that all the induced edge labels are different. Induced edge label is the absolute value of the difference between the labels (numbers) of the two end-vertices of the edge. A graph is graceful if it admits graceful labeling. The Graceful Tree Conjecture claims that all trees are graceful.

There are two approaches to solving the Graceful Tree Conjecture. The first is to prove gracefulness and obtain graceful labeling algorithms for certain classes of trees; if once gracefulness of all classes of trees is shown, then the Conjecture is proved. For today, gracefulness is proved for stars, paths, caterpillars, olive trees, some subclasses of lobsters (firecrackers, (2,2)-caterpillars, lobsters with perfect matchings), banana and generalized banana trees, and some other classes. Many methods of combining few graceful trees to obtain a new bigger graceful tree have been found.

Another approach to solving the conjecture is to use computer to check if all trees with number of vertices not exceeding a given value are graceful. This approach can provide new graceful labeling algorithms and can be also used to disprove the Conjecture, once at least one tree that does not admit graceful labeling is found. However, no such tree has been found so far. It has been proved that all the trees having not more than 35 vertices are graceful.

Despite all the positive results, some researchers express serious doubts about the truthfulness of the Conjecture. They point out that the most graceful labeling methods have been designed for trees with regular or very simple structure, while there are no proofs of gracefulness for sufficiently irregular trees. However, the majority or researchers tend to believe that the Graceful Tree Conjecture is true and will be once proved completely.

Keywords: graceful tree,  graceful marking, graph, caterpillars, vertices.

Download full text! (In Russian).

1. Rosa, A., 1967. “On certain valuations of the vertices of a graph. Theory of Graphs”. (Internat. Sympos. Rome, 1966). Eds. Gordon and Breach. New York; Dunod, Paris, pp. 349–355.
2. Golomb, S.W., 1972. “How to number a graph. Graph Theory and Computing”. New York: Academic Press, pp. 23–37.
   https://doi.org/10.1016/B978-1-4832-3187-7.50008-8
3. Fang, W. A computational approach to the graceful tree – Access Mode: arXiv:1003.3045v2.
4. Morgan, D., 2002. “All lobsters with perfect matchings are graceful”. Electron. Notes Discrete Math., 11, pp. 503–508.
   https://doi.org/10.1016/S1571-0653(04)00095-2
5. Pastel, M., Raynaud, H., 1978. “Numerotation gracieuse des oliviers, in colloq”. Grenoble: Publ. University de Grenoble, pp. 218–223.
6. Bermond, J.C., 1979. “Graceful graphs, radio antennae and French windmills”. Graph Theory and Comb. London: Pitman, pp. 18–37.
7. Chen, W.C., Lü, H.I., Yeh, Y.N. Operations of interlaced trees and graceful trees. Southeast Asian Bull. Math. 21., pp. 337–348.
8. Nastoyashchyi, V.A., Petrenyuk, A.Ya., Petrenyuk, D.A., 2012. “Dovedennya isnuvannya pivobertovoyi T-faktoryzatsiyi dlya vsikh pivsymetrychnykh derev poryadku n = 22”. Kombinatorni konfihuratsiyi ta yikh zastosuvannya: Materialy Deviatoho Mizhvuz. nauk.-prakt. sem., 16–17 kvitnya 2010. Kirovohrad, pp. 97–103. (In Ukrainian).
9. Sethuraman, G., Jesintha, J., 2009. “All extended banana trees are graceful”. Proc. Internat. Conf. Math. Comp. Sci., 1, pp. 4–8.
10. Bahl, M., Lake, S., Wertheim, A. Gracefulness of Families of Spiders. http://facstaff.unca.edu/pbahls/papers/Spiders.pdf.
11. Bermond, J.C., Sotteau, D., 1975. “Graph Decompositions and G-design”. Proc. 5th British Comb. Conf., pp. 52–72.
12. Hrnčiar, P., Haviar, A., 2001. “All trees of diameter five are graceful”. Discrete Math., 233, pp. 133–150.
    https://doi.org/10.1016/S0012-365X(00)00233-8
13. Donets, G.A., Petrenyuk, D.A., 2010. Postroyeniye T-faktorizatsiy polnogo grafa i problema Rosa. Upravlausie sistemy i masiny, 4, pp. 21–24. (In Russian).
14. Burzio, M., Ferrarese, G., 1998. “The subdivision graph of a graceful tree is a graceful tree”. Discrete Math., 181, pp. 275–281.
    https://doi.org/10.1016/S0012-365X(97)00069-1
15. Koh, K.M., Rogers, D.G., Tan, T., 1877. “On Graceful Trees”. Nanta Mathematica, 10, pp. 207–211.
16. Koh, K.M., Tan, T., Rogers, D.G., 1979. “Two theorems on graceful trees”. Discrete Math., 25, pp. 141–148.
    https://doi.org/10.1016/0012-365X(79)90016-5
17. Mavronicolas, Michael, L., 2009. “A substitution theorem for graceful trees and its applications”. Discrete Mathe¬matics, 309 (12), pp. 3757–3766.
18. Vietri, A., 2008. “Sailing towards, and then against, the Graceful Tree Conjecture: some promiscuous results”. I.C.A. Bulletin, 53. pp. 31–46.
19. Krishnaa, A., 2004. “A. study of the major graph labelings of trees”. Informatica, 15, pp. 515–524.
20. Jesse Gilbert., 2009. A Complete Proof of the Graceful Tree Conjecture Using the Concept of Edge Degree, Jan. 9, 2009. Access Mode: arXiv:0709.2201.
21. Alfalayleh, M., Brankovic, L., Giggins H. et al., 2004. “Towards the Graceful Tree Conjecture: A survey”. Proc. AWOCA 2004, 7–9 July, Ballina, Austrtalia.

Recieved 09.04.2015