A Generalization of the Hamilton–Waterloo Problem on Complete Equipartite Graphs |
| |
Authors: | Melissa S. Keranen Adrián Pastine |
| |
Affiliation: | Michigan Technological University, Department of Mathematical Sciences, Houghton, MI, U.S.A. |
| |
Abstract: | The Hamilton–Waterloo problem asks for which s and r the complete graph can be decomposed into s copies of a given 2‐factor F1 and r copies of a given 2‐factor F2 (and one copy of a 1‐factor if n is even). In this paper, we generalize the problem to complete equipartite graphs and show that 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, , , and . 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. |
| |
Keywords: | generalized Oberwolfach Problem Hamilton– Waterloo Problem graph decomposition complete multipartite graphs |
|
|