Decomposing Ku+w − Ku into cycles of prescribed lengths

Daniel Horsley, Rosalind A Hoyte

Research output: Contribution to journalArticleResearchpeer-review

1 Citation (Scopus)

Abstract

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
Volume340
Issue number8
DOIs
Publication statusPublished - 1 Aug 2017

Keywords

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

Cite this