Decomposing Ku+w − Ku into cycles of prescribed lengths

Daniel Horsley, Rosalind A Hoyte

Research output: Contribution to journalArticleResearchpeer-review

1 Citation (Scopus)


We prove that the complete graph with a hole Ku+w − Ku can be decomposed into cycles of arbitrary specified lengths provided that the obvious necessary conditions are satisfied, each cycle has length at most min(u, w), and the longest cycle is at most three times as long as the second longest. This generalises existing results on decomposing the complete graph with a hole into cycles of uniform length, and complements work on decomposing complete graphs, complete multigraphs, and complete multipartite graphs into cycles of arbitrary specified lengths.

Original languageEnglish
Pages (from-to)1818-1843
Number of pages26
JournalDiscrete Mathematics
Issue number8
Publication statusPublished - 1 Aug 2017


  • Complete graph with a hole
  • Cycle decomposition
  • Graph decomposition

Cite this