An asymptotic solution to the cycle decomposition problem for complete graphs

Darryn Bryant, Daniel Horsley

Research output: Contribution to journalArticleResearchpeer-review

11 Citations (Scopus)

Abstract

Let m1,m2, . . . ,mt be a list of integers. It is shown that there exists an integer N such that for all n N, the complete graph of order n can be decomposed into edge-disjoint cycles of lengths m1,m2, . . . ,mt if and only if n is odd, 3 mi n for i = 1, 2, . . . , t, and m1 + m2 + A? A? A?mt = 2 taken from n elements. In 1981, Alspach conjectured that this result holds for all n, and that a corresponding result also holds for decompositions of complete graphs of even order into cycles and a perfect matching
Original languageEnglish
Pages (from-to)1258 - 1284
Number of pages27
JournalJournal of Combinatorial Theory - Series A
Volume117
Issue number8
DOIs
Publication statusPublished - 2010
Externally publishedYes

Cite this