The Hamilton-Waterloo problem with even cycle lengths

DOI10.1016/J.DISC.2019.04.013MaRDI QIDQ2319702zbMATH OpenOpenAlexWikidataFDO

Authors Peter Danziger, Tommaso Traetta, Andrea Burgess

Publication date 20 August 2019

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

Hamilton-Waterloo problem2-factorizations(resolvable) cycle decompositions

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: The Hamilton-Waterloo Problem HWP$$ asks for a 2-factorization of the complete graph $K_v$ or $K_v-I$, the complete graph with the edges of a 1-factor removed, into $alpha$ $C_m$-factors and $$ $C_n$-factors, where $3leqm<n$. In the case that $m$ and $n$ are both even, the problem has been solved except possibly when $$ or when $alpha$ and $$ are both odd, in which case necessarily $vequiv2pmod4$. In this paper, we develop a new construction that creates factorizations with larger cycles from existing factorizations under certain conditions. This construction enables us to show that there is a solution to HWP$$ for odd $alpha$ and $$ whenever the obvious necessary conditions hold, except possibly if $$; $$ and $gcd(m,n)=1$; $alpha=1$; or $v=2mn/gcd(m,n)$. This result almost completely settles the existence problem for even cycles, other than the possible exceptions noted above.

Recommendations

• On the Hamilton-Waterloo problem: the case of two cycles sizes of different parity
• On the Hamilton-Waterloo problem with odd cycle lengths
• On the Hamilton-Waterloo problem with cycle lengths of distinct parities
• The Hamilton-Waterloo problem with \(C_4\) and \(C_m\) factors
• On the Hamilton-Waterloo problem with odd orders

Cites work

• scientific article; zbMATH DE number 3922695 (Why is no real title available?)
• scientific article; zbMATH DE number 1394637 (Why is no real title available?)
• A complete solution to the two-table Oberwolfach problems
• A cyclic solution for an infinite class of Hamilton-Waterloo problems
• A generalization of the Hamilton-Waterloo problem on complete equipartite graphs
• A note on the Hamilton-Waterloo problem with \(C_8\)-factors and \(C_m\)-factors
• Asymptotic Existence of Resolvable Graph Designs
• Complete solutions to the Oberwolfach problem for an infinite set of orders
• Further results on almost resolvable cycle systems and the Hamilton–Waterloo problem
• Hamiltonian decomposition of Cayley graphs of degree 4
• Infinitely many cyclic solutions to the Hamilton-Waterloo problem with odd length cycles
• Octahedral, dicyclic and special linear solutions of some Hamilton-Waterloo problems
• On bipartite 2-factorizations of \(K_{n} - I\) and the Oberwolfach problem
• On factorisations of complete graphs into circulant graphs and the Oberwolfach problem
• On the Hamilton-Waterloo problem for bipartite 2-factors
• On the Hamilton-Waterloo problem with cycle lengths of distinct parities
• On the Hamilton-Waterloo problem with odd cycle lengths
• On the Hamilton-Waterloo problem with odd orders
• On the Hamilton-Waterloo problem with triangle factors and \(C_{3x}\)-factors
• The Hamilton-Waterloo Problem for C3-Factors and Cn-Factors
• The Hamilton-Waterloo problem for Hamilton cycles and triangle-factors
• The Hamilton-Waterloo problem for cycle sizes 3 and 4
• The Hamilton-Waterloo problem with 4-cycles and a single factor of \(n\)-cycles
• The Hamilton-Waterloo problem with \(C_4\) and \(C_m\) factors
• The Oberwolfach problem and factors of uniform odd length cycles
• The equipartite Oberwolfach problem with uniform tables
• The existence of \(C_ k\)-factorizations of \(K_{2n}-F\)

Cited in

(17)

• The Hamilton-Waterloo problem: The case of triangle-factors and one Hamilton cycle
• On the Hamilton-Waterloo problem for bipartite 2-factors
• On the Hamilton-Waterloo problem with cycle lengths of distinct parities
• On the Hamilton-Waterloo problem with odd cycle lengths
• A cyclic solution for an infinite class of Hamilton-Waterloo problems
• Infinitely many cyclic solutions to the Hamilton-Waterloo problem with odd length cycles
• The Hamilton-Waterloo problem with \(C_4\) and \(C_m\) factors
• A survey on constructive methods for the Oberwolfach problem and its variants
• Hamilton-Waterloo problem: bipartite case
• On the Hamilton-Waterloo problem
• Constructing uniform 2-factorizations via row-sum matrices: solutions to the Hamilton-Waterloo problem
• The Hamilton-Waterloo problem with triangle-factors and Hamilton cycles: the case \(n\equiv 3\pmod{18}\)
• The Hamilton-Waterloo problem for Hamilton cycles and \(C_{4k}\)-factors.
• On the Hamilton-Waterloo problem with odd orders
• The Hamilton-Waterloo problem with 4-cycles and a single factor of \(n\)-cycles
• On the Hamilton-Waterloo problem: the case of two cycles sizes of different parity
• A generalization of the Hamilton-Waterloo problem on complete equipartite graphs

This page was built for publication: The Hamilton-Waterloo problem with even cycle lengths

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