On the generalized Oberwolfach problem

Andrea C. Burgess, Peter Danziger, Tommaso Traetta

Abstract


The generalized Oberwolfach problem OPt(2w + 1; N1, N2, …, Nt; α1, α2, …, αt) asks for a factorization of K2w + 1 into αi CNi-factors (where a CNi-factor of K2w + 1 is a spanning subgraph whose components are cycles of length Ni ≥ 3) for i = 1, 2, …, t. Necessarily, N = lcm(N1, N2, …, Nt) is a divisor of 2w + 1 and w = Σ ti = 1αi.

For t = 1 we have the classic Oberwolfach problem. For t = 2 this is the well-studied Hamilton-Waterloo problem, whereas for t ≥ 3 very little is known.

In this paper, we show, among other things, that the above necessary conditions are sufficient whenever 2w + 1 ≥ (t + 1)N, αi > 1 for every i ∈ {1, 2, …, t}, and gcd (N1, N2, …, Nt) > 1. We also provide sufficient conditions for the solvability of the generalized Oberwolfach problem over an arbitrary graph and, in particular, the complete equipartite graph.


Keywords


2-factorizations, resolvable cycle decompositions, cycle systems, (generalized) Oberwolfach problem, Hamilton-Waterloo problem

Full Text:

PDF


DOI: https://doi.org/10.26493/1855-3974.1426.212

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications