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 |
|
|
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.