A generalization of the Hamilton-Waterloo problem on complete equipartite graphs

DOI10.1002/JCD.21560MaRDI QIDQ4591508zbMATH OpenOpenAlexFDO

Authors Adrián Pastine, Melissa S. Keranen

Publication date 17 November 2017

Published in Journal of Combinatorial Designs (Search for Journal in Brave)

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

zbMATH Keywords

graph decompositioncomplete multipartite graphsHamilton-Waterloo problemgeneralized Oberwolfach problem

Mathematics Subject Classification ID

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

Abstract: The Hamilton-Waterloo problem asks for which $s$ and $r$ the complete graph $K_n$ can be decomposed into $s$ copies of a given 2-factor $F_1$ and $r$ copies of a given 2-factor $F_2$ (and one copy of a 1-factor if $n$ is even). In this paper we generalize the problem to complete equipartite graphs $K_{(n:m)}$ and show that $K_{(xyzw:m)}$ can be decomposed into $s$ copies of a 2-factor consisting of cycles of length $xzm$; and $r$ copies of a 2-factor consisting of cycles of length $yzm$, whenever $m$ is odd, $s,req1$, $gcd(x,z)=gcd(y,z)=1$ and $xyzeq0pmod4$. We also give some more general constructions where the cycles in a given two factor may have different lengths. We use these constructions to find solutions to the Hamilton-Waterloo problem for complete graphs.

Recommendations

• On the Hamilton-Waterloo problem: the case of two cycles sizes of different parity
• On the Hamilton-Waterloo problem for bipartite 2-factors
• The Hamilton-Waterloo problem with even cycle lengths
• On the Hamilton-Waterloo problem with triangle factors and \(C_{3x}\)-factors
• On the Hamilton-Waterloo problem with odd cycle lengths

Cited in

(11)

• On the Hamilton-Waterloo problem for bipartite 2-factors
• A note on the Hamilton-Waterloo problem with \(C_8\)-factors and \(C_m\)-factors
• Resolvable cycle decompositions of complete multigraphs and complete equipartite multigraphs via layering and detachment
• On the Hamilton-Waterloo problem with cycle lengths of distinct parities
• The Hamilton-Waterloo problem with even cycle lengths
• On the minisymposium problem
• Hamilton-Waterloo problem: bipartite case
• Constructing uniform 2-factorizations via row-sum matrices: solutions to the Hamilton-Waterloo problem
• On the generalized Oberwolfach problem
• On the Hamilton-Waterloo problem: the case of two cycles sizes of different parity
• Completing the spectrum of almost resolvable cycle systems with odd cycle length

This page was built for publication: A generalization of the Hamilton-Waterloo problem on complete equipartite graphs

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