New Advances in Kotzig's Conjecture

Abstract

In 1973 Kotzig conjectures that the complete graph $K_{2n+1}$ can be cyclically decomposed into $2n+1$ copies of any tree of size $n$. Rosa proved that this decomposition exists if and only if there exists a $\rho$-labeling of the tree. In this work we prove that if $T'$ is a graceful tree, then any tree $T$ obtained from $T'$ by attaching a total of $k \geq 1$ pendant vertices to any collection of $r$ vertices of $T'$, where $1 \leq r \leq k$, admits a $\rho$-labeling. As a consequence of this result, many new families of trees with this kind of labeling are produced, which indicates the strong potential of this result. Moreover, the technique used to prove this result, gives us an indication of how to determine whether a given tree of size $n$ decomposes the complete graph $K_{2n+1}$. We also prove the existence of a $\rho$-labeling for two subfamilies of lobsters and present a method to produce $\rho$-labeled trees attaching pendant vertices and pendant copies of the path $P_3$ to some of the vertices of any graceful tree.\\ In addition, for any given tree $T$, we use bipartite labelings to show that this tree is a spanning tree of a graph $G$ that admits an $\alpha$-labeling. This is not a new result; however, the construction presented here optimizes (reduces) the size of $G$ with respect to all the similar results that we found in the literature.

Keywords

• Decomposition,Graceful graph,Graceful labeling

References

1. [1] G. Ringel, Problem 25, in Theory of Graphs and Its Applications, Proc. Symposium Smolenice 1963, Prague (1964), 162.
2. [2] A. Kotzig, On certain vertex valuations of finite graphs, Util. Math., 4 (1973), 67-73.
3. [3] A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs (Internat. Symposium, Rome, July 1966), Gordon and Breach, N. Y. and Dunod Paris (1967), 349-355.
4. [4] C. Barrientos, E. Krop, Improved bounds for relaxed graceful trees, Graphs Combin., 33 (2017), 287-305.
5. [5] C. Barrientos, S. Minion, New attack on Kotzig’s conjecture, Electron. J. Graph Theory Appl., 4(2) (2016), 119-131.
6. [6] G. Chartrand, L. Lesniak, Graphs & Digraphs, 2nd ed. Wadsworth & Brooks/Cole, Monterey, 1986.
7. [7] J. A. Gallian, A dynamic survey of graph labeling, Electronic J. Combin., 21(#DS6), 2018.
8. [8] Y. Caro, Y. Roditty, J. Sch¨onheim, Starters for symmetric (n,G,1)-designs. r-labelings revisited, (in press).

9. [9] A. K´ezdy, r-valuations for some stunted trees, Discrete Math., 306 (2006), 2786- 2789.
10. [10] P. Bahl, S. Lake, A. Wertheim, Gracefulness of families of spiders, Involve, 3 (2010), 241-247.
11. [11] S. El-Zanati, C. Vanden Eynden, N. Punnim, On the cyclic decomposition of complete graphs into bipartite graphs, Australas. J. Combin., 24 (2001), 209-219.
12. [12] C. Huang, A. Rosa, Decomposition of complete graphs into trees, Ars Combin., 5 (1978), 23-63.
13. [13] D. Morgan, All lobsters with perfect matchings are graceful, Electron. Notes Discrete Math., 11 (2002), 6 pp.
14. [14] M. Burzio, G. Ferrarese, The subdivision graph of a graceful tree is a graceful tree, Discrete Math., 181 (1998), 275-281.
15. [15] W. Fang, A computational approach to the graceful tree conjecture, arXiv:1003.3045v1 [cs.DM].
16. [16] K. Eshghi, P. Azimi, Applications of mathematical programming in graceful labeling of graphs, J. Applied Math., 1 (2004), 1-8.
17. [17] C. Huang, A. Kotzig, A. Rosa, Further results on tree labellings, Util. Math., 21c (1982), 31-48.
18. [18] S. K. Vaidya, N. A. Dani, Cordial labeling and arbitrary super subdivision of some graphs, Inter. J. Information Sci. Comput. Math., 2(1) (2010), 51-60.
19. [19] D. J. Jin, F. H. Meng, J. G. Wang, The gracefulness of trees with diameter 4, Acta Sci. Natur. Univ. Jilin., (1993), 17-22.
20. [20] P. Hrnˇciar, A. Haviar, All trees of diameter five are graceful, Discrete Math., 233 (2001), 133-150.
21. [21] J. C. Bermond, D. Sotteau, Graph decompositions and G-design, Proceedings of the Fifth British Combinatorial Conference, 1975, Congr. Numer., XV (1976) 53-72.
22. [22] C. Balbuena, P. Garc´ıa-Vazquez, X. Marcote, J. C. Valenzuela, Trees having an even or quasi even degree sequence are graceful, Applied Math. Letters, 20 (2007), 370-375.
23. [23] G. Sethuraman, J. Jesintha, A new class of graceful rooted trees, J. Disc. Math. Sci. Crypt., 11 (2008), 421-435.
24. [24] S. B. Rao, U. K. Sahoo, Embeddings in Eulerian graceful graphs, Australasian J. Comb., 62(1) (2015), 128-139.
25. [25] G. Sethuraman, P. Ragukumar, Every tree is a subtree of graceful tree, graceful graph and alpha-labeled graph, Ars Combin., 132 (2017), 105-109.