Decomposing complete tripartite graphs into 5-cycles when the partite sets have similar size

作者：Billington Elizabeth J^*; Cavenagh Nicholas J

来源：Aequationes Mathematicae, 2011, 82(3): 277-289.

DOI：10.1007/s00010-011-0098-6

• Graph decomposition
• cycle decomposition
• complete tripartite graph

The problem of finding necessary and sufficient conditions to decompose a complete tripartite graph into 5-cycles was first posed at a conference in 1994 (Mahmoodian and Mirzakhani in Combinatorics Advances, 1995). Since then, many cases of the problem have been solved by various authors; however the case when the partite sets have odd and distinct sizes remains open. In this note, we introduce a new approach to the problem by embedding previously known decompositions into larger ones. Via this approach, we show that when the partite sets have asymptotically similar sizes, the conjectured necessary conditions for a decomposition are also sufficient.

• 出版日期2011-12