Decomposing K_u + w - K_u into cycles of prescribed lengths

DOI10.1016/J.DISC.2017.03.011MaRDI QIDQ2397526zbMATHOpenAlexFDO

Authors Daniel Horsley, Rosalind A. Hoyte

Publication date 22 May 2017

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1603.03908

zbMATH Keywords

graph decompositioncycle decompositioncomplete graph with a hole

Mathematics Subject Classification ID

Distance in graphs (05C12) Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

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.

Recommendations

• Decomposing various graphs into short even-length cycles
• Decompositions of complete multigraphs into cycles of varying lengths
• Decompositions of complete graphs into long cycles
• Cycle decompositions. III: Complete graphs and fixed length cycles.
• Decomposing the complete graph into cycles of many lengths

Cites work

• scientific article; zbMATH DE number 3847402 (Why is no real title available?)
• scientific article; zbMATH DE number 3428958 (Why is no real title available?)
• 5-cycle systems with holes
• An asymptotic solution to the cycle decomposition problem for complete graphs
• Cycle decompositions of complete multigraphs
• Cycle decompositions. V: Complete graphs into cycles of arbitrary lengths
• Decomposing complete equipartite multigraphs into cycles of variable lengths: the amalgamation-detachment approach
• Decomposing various graphs into short even-length cycles
• Decomposition of K//(m,n)(K*//(m,n)) into cycles (circuits) of length 2k
• Decomposition of \(K_{m,n}\) into short cycles
• Decompositions into 2-regular subgraphs and equitable partial cycle decompositions
• Decompositions of complete graphs into long cycles
• Doyen-Wilson results for odd length cycle systems
• Embeddings of Steiner triple systems
• Embeddings of \(m\)-cycle systems and incomplete \(m\)-cycle systems: \(m\leq 14\)
• The Solution of a Timetabling Problem

Cited in

(2)

• Decomposing various graphs into short even-length cycles
• Enclosings of decompositions of complete multigraphs in 2-edge-connected \(r\)-factorizations

This page was built for publication: Decomposing \(K_{u + w} - K_u\) into cycles of prescribed lengths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2397526)