A Generalization of the Hamilton–Waterloo Problem on Complete Equipartite Graphs

DOI10.1002/JCD.21560zbMATH Open1374.05179arXiv1605.01781OpenAlexW2964052122MaRDI QIDQ4591508FDOQ4591508

Adrián Pastine, Melissa S. Keranen

Publication date: 17 November 2017

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

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.

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)

Cited In (8)

• Resolvable cycle decompositions of complete multigraphs and complete equipartite multigraphs via layering and detachment
• A note on the Hamilton-Waterloo problem with \(C_8\)-factors and \(C_m\)-factors
• On the Hamilton-Waterloo problem with cycle lengths of distinct parities
• The Hamilton-Waterloo problem with even cycle lengths
• On the minisymposium 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)