On the Hamilton–Waterloo problem with odd cycle lengths
Journal of Combinatorial Designs · 2018-02 · 26 (2) · 51-83
DOI: 10.1002/jcd.21586 ↗At a glance
Journal article in Journal of Combinatorial Designs, published online on 2017-10-10. Written by A. C. Burgess and 2 co-authors. Cited 9 times so far (Crossref); 48 references. Funded by: Istituto Nazionale di Alta Matematica "Francesco Severi", Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada.
Abstract (original language)
Let denote the complete graph if v is odd and , the complete graph with the edges of a 1‐factor removed, if v is even. Given nonnegative integers , the Hamilton–Waterloo problem asks for a 2‐factorization of into α ‐factors and β ‐factors, with a ‐factor of being a spanning 2‐regular subgraph whose components are ℓ‐cycles. Clearly, , , and are necessary conditions. In this paper, we extend a previous result by the same authors and show that for any odd the above necessary conditions are sufficient, except possibly when , or when . Note that in the case where v is odd, M and N must be odd. If M and N are odd but v is even, we also show sufficiency but with further possible exceptions. In addition, we provide results on 2‐factorizations of the complete equipartite graph and the lexicographic product of a cycle with the empty graph.
Funding
- Istituto Nazionale di Alta Matematica "Francesco Severi"
- Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada
Cite
APA
Burgess, A. C., Danziger, P., & Traetta, T. (2018). On the Hamilton–Waterloo problem with odd cycle lengths. Journal of Combinatorial Designs, 26(2), 51-83. https://doi.org/10.1002/jcd.21586
Vancouver
Burgess AC, Danziger P, Traetta T. On the Hamilton–Waterloo problem with odd cycle lengths. Journal of Combinatorial Designs. 2018;26(2):51-83. doi:10.1002/jcd.21586
BibTeX
@article{Burgess2018,
author = {Burgess, A. C. and Danziger, P. and Traetta, T.},
title = {On the Hamilton–Waterloo problem with odd cycle lengths},
journal = {Journal of Combinatorial Designs},
year = {2018},
volume = {26},
number = {2},
pages = {51--83},
doi = {10.1002/jcd.21586}
}
EUVIMED