Premium
A Generalization of the Hamilton–Waterloo Problem on Complete Equipartite Graphs
Author(s) -
Keranen Melissa S.,
Pastine Adrián
Publication year - 2017
Publication title -
journal of combinatorial designs
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.618
H-Index - 34
eISSN - 1520-6610
pISSN - 1063-8539
DOI - 10.1002/jcd.21560
Subject(s) - combinatorics , mathematics , generalization , hamiltonian path , factor (programming language) , discrete mathematics , graph , computer science , mathematical analysis , programming language
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 , r ≠ 1 , gcd ( x , z ) = gcd ( y , z ) = 1 , and xyz ≠ 0 ( mod 4 ) . 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.