New Advances in Kotzig’s Conjecture

Abstract

In 1973 Kotzig conjectures that the complete graph K2n+1 can be cyclically decomposedinto 2n+1 copies of any tree of size n. Rosa proved that this decomposition exists if andonly if there exists a ρ-labeling of the tree. In this work we prove that if $T^'$is a gracefultree, then any tree T obtained from $T^'$ by attaching a total of k ≥ 1 pendant vertices to anycollection of r vertices of $T^'$, where 1 ≤ r ≤ k, admits a ρ-labeling. As a consequenceof this result, many new families of trees with this kind of labeling are produced, whichindicates the strong potential of this result. Moreover, the technique used to prove thisresult, gives us an indication of how to determine whether a given tree of size n decomposesthe complete graph K2n+1. We also prove the existence of a ρ-labeling for two subfamiliesof lobsters and present a method to produce ρ-labeled trees attaching pendant vertices andpendant copies of the path P3 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 aspanning tree of a graph G that admits an α-labeling. This is not a new result; however, theconstruction presented here optimizes (reduces) the size of G with respect to all the similarresults that we found in the literature.