Decomposing K_u+w-K_u into cycles of various lengths

2016/03/12 by Daniel Horsley, Horsley, Daniel, Rosalind A. Hoyte +1
Computer Science · Engineering · Mathematics · #05B30 (Secondary) #05C51 (Primary) 05C38 #Advanced Graph Theory Research #Coding theory and cryptography #Combinatorics (math.CO) #FOS: Mathematics #graph theory and CDMA systems #math.CO #msc:05B30 #msc:05C38 #msc:05C51

paper · pdf · doi:10.48550/arxiv.1603.03908

41 pages, 0 figures. arXiv admin note: text overlap with arXiv:1411.3785

arxiv created 2016/03/12 · openalex publication_date 2016/03/12 · arxiv updated 2016/03/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We prove that the complete graph with a hole K_u+w-K_u 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.

Citations

• Doyen-Wilson results for odd length cycle systems

Related

• Decomposing various graphs into short even-length cycles
• Cycle packings of the complete multigraph
• Decompositions of complete multigraphs into cycles of varying lengths
• Cycle decompositions of cartesian products of two cycles
• Decomposition of a complete bipartite multigraph into arbitrary cycle sizes