Every tree on n edges decomposes K_nx,nx and K_2nx+1

2024/09/03 by Parikshit Chalise, Chalise, Parikshit, A. D. Clark +3
Mathematics · Computer Science · #Graph theory and applications #Advanced Graph Theory Research #Interconnection Networks and Systems

paper · pdf · doi:10.48550/arxiv.2409.01981

Abstract

We prove that every tree on n edges decomposes K_nx,nx and K_{2nx + 1} for all positive integers x. The said decompositions are obtained by proving that every tree admits a β-labeling (oriented beta-labeling). Our proof employs the polynomial method by identifying trees as functions in the transformation monoid ℤ_n^ℤ_n. A proof of the graceful tree conjecture (1967) follows as an immediate consequence of the current result. Finally, we introduce additional algebraic properties derived from the decomposition results.

Related

• On graceful labelings of trees
• A Proof of the Tree Packing Conjecture
• Decomposing highly edge-connected graphs into homomorphic copies of a fixed tree
• A complete proof of The Graceful Tree Conjecture using the concept of Edge Degree
• Canonical tree-decompositions of a graph that display its k-blocks