Decomposing K_u + w - K_u into cycles of prescribed lengths

DOI10.1016/J.DISC.2017.03.011zbMATH Open1362.05103arXiv1603.03908OpenAlexW2606525547MaRDI QIDQ2397526FDOQ2397526

Daniel Horsley, Rosalind A. Hoyte

Publication date: 22 May 2017

Published in: Discrete Mathematics (Search for Journal in Brave)

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.

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

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

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)

Cites Work

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

Cited In (1)

• 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)