Decomposing various graphs into short even-length cycles

2012/04/16 by Daniel Horsley, Horsley, Daniel · 1 citation
Mathematics · #05C51 (Primary) 05C38 (Secondary) #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C38 #msc:05C51

paper · pdf · doi:10.48550/arxiv.1204.3368

30 pages, no figures

arxiv created 2012/04/16 · arxiv updated 2012/04/17

Abstract

We prove that a complete bipartite graph can be decomposed into cycles of arbitrary specified lengths provided that the obvious necessary conditions are satisfied, the length of each cycle is at most the size of the smallest part, and the longest cycle is at most three times as long as the second longest. We then use this result to obtain results on incomplete even cycle systems with a hole and on decompositions of complete multipartite graphs into cycles of uniform even length.

Cited by

• m-Cycle Packings of (λ+μ)K_v+u-λK_v: m even

Related

• Decomposing K_u+w-K_u into cycles of various lengths
• Decomposition of a complete bipartite multigraph into arbitrary cycle sizes
• Decompositions of complete multigraphs into cycles of varying lengths
• Cycle packings of the complete multigraph
• Arithmetic Progressions of Cycle Lengths in Graphs