ARS MATHEMATICA CONTEMPORANEA
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 17 (2019) 67-78
https://doi.org/10.26493/1855-3974.1426.212
(Also available at http://amc-journal.eu)
On the generalized Oberwolfach problem
Andrea C. Burgess *
Department of Mathematics and Statistics, University of New Brunswick, 100 Tucker Park Rd., Saint John, NB E2L 4L5, Canada
Peter Danziger t
Department of Mathematics, Ryerson University, 350 Victoria St., Toronto, ON M5B 2K3, Canada
Tommaso Traetta * DICATAM, University of Brescia, via Branze 43, 25123 Brescia, Italy
Received 19 June 2017, accepted 22 April 2019, published online 20 June 2019
The generalized Oberwolfach problem OPt(2w + 1; N1, N2,..., Nt; a1,a2,..., at) asks for a factorization of K2w+1 into a® CNi -factors (where a CNi -factor of K2w+1 is a spanning subgraph whose components are cycles of length N > 3) for i = 1,2,... , t. Necessarily, N = lcm(N1, N2,..., Nt) is a divisor of 2w + 1 and w = J21=1 a®.
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, a® > 1 for every i G {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. Math. Subj. Class.: 05C51, 05C70
*The author gratefully acknowledges support from NSERC Discovery Grant RGPIN-435898-2013. tThe author gratefully acknowledges support from NSERC Discovery Grant RGPIN-2016-04178.
* The author gratefully acknowledges the support of a Marie Curie fellowship of the Istituto Nazionale di Alta Matematica, and the support of GNSAGA.
E-mail addresses: andrea.burgess@unb.ca (Andrea C. Burgess), danziger@ryerson.ca (Peter Danziger), tommaso.traetta@unibs.it (Tommaso Traetta)
Abstract
©® This work is licensed under https://creativecommons.org/licenses/by/4.0/
104
ArsMath. Contemp. 17 (2019) 68-114
1 Introduction
We denote by V(G) and E(G) the vertex set and the edge set of a simple graph G, respectively. Also, we denote by tG the vertex-disjoint union of t > 0 copies of G.
A factor F of G is a spanning subgraph of G, namely, a subgraph of G such that V(F) = V(G); also, if F is ¿-regular, we call F an i-factor. In particular, a 1-factor of G (also called a perfect matching) is the vertex-disjoint union of edges of G whose vertices partition V(G), while a 2-factor of G is the vertex-disjoint union of cycles whose vertices span V(G). A 2-factor of G containing only one cycle is usually called a Hamiltonian cycle. We say that a factor is uniform when its components are pairwise isomorphic. Hence, a 1-factor is uniform, whereas a 2-factor might not be.
As usual, we denote by Kv the complete graph on v vertices; also, we use K* to denote the graph Kv when v is odd and Kv - I, where I is a 1-factor of Kv, when v is even. Further, we denote by Ks[z] the complete equipartite graph with s parts of size z. Note that, Kv ~ Kv [1] or Kv/2 [2], according to whether v is odd or even, respectively. Finally, we denote by C a cycle of length ¿ > 3 (briefly, an ¿-cycle), and by (x0, x1..., x^_i) the ¿-cycle with edges x0x1, x1x2,..., x^_1x0. A uniform 2-factor whose cycles have all length ¿ is referred to as a C¿-factor.
A 2-factorization of a simple graph G is a set F of 2-factors of G whose edge sets partition E(G). If F contains only C^-factors, we speak of a C¿-factorization of G. It is well known that a regular graph has a 2-factorization if and only if every vertex has even degree. However, if we specify t 2-factors, say F1, F2,..., Ft, and ask for the factorization F to contain ai factors isomorphic to Fj, then the problem becomes much harder. Much attention has been given to the cases where t G {1,2} and either G = Kv or G = Ks [z].
For t = 1, we have the "classic" Oberwolfach problem, which is well known to be hard. A survey of the most relevant results on this problem, updated to 2006, can be found in [15, Section VI.12]. For more recent results we refer the reader to [6, 9, 11, 29].
Although the Oberwolfach problem is still open, it has been completely solved for uniform factors when G = K [2, 3, 22] or when G is the complete equipartite graph [24]. We recall these results below.
Theorem 1.1 ([2, 3, 22, 24]). Let ¿, s and z be positive integers with ¿ > 3. There exists a C¿-factorization of Ks[z] if and only if ¿ | sz, (s — 1)z is even, further ¿ is even when s = 2, and (¿, s, z) G {(3, 3, 2), (3, 6, 2), (3, 3, 6), (6, 2, 6)}.
For t > 1, we refer to this problem as the generalized Oberwolfach problem. More precisely, given a simple graph G, given t 2-factors of G, say F1, F2,..., Ft, and given t non-negative integers a1, a2,..., at, the generalized Oberwolfach problem, denoted by OPt(G; F1, F2,..., Ft; a1, a2,..., at), or briefly by OPt(G; (Fj); («,)), asks for a factorization of G into ai Fj-factors for i G {1, 2,... ,t}. In the case where each Fj is uniform, namely, Fi is a CNi-factor, we denote the problem by OPt(G; N1, N2,..., Nt; a1, a2,..., at), or briefly by OPt(G; (Ni); (ai)). Further, we use v in place of G when G = Kv*. The following necessary conditions are trivial.
Theorem 1.2. If there exists a solution to OPt(G; (Ni); (ai)), then the following conditions hold:
(1)	G is regular of degree 2 • J2i=1 ai,
(2)	lcm(N1, N2,..., Nt) is a divisor of the order of G.
A. C. Burgess et al.: On the generalized Oberwolfach problem
69
The case in which t = 2 is known as the Hamilton-Waterloo problem. Although it has received much interest recently, it is still open even in the uniform case. Some of the most important results up to 2006 can be found in [15, Section VI.12]. More recent results can be found in [4, 7, 8, 10, 12, 13, 16, 23, 25]. For more details and some history on the problem, we refer the reader to [12, 13].
Much less is known on OPt(v; (Fi); (a^) when t > 2. In [1, 18, 19] the problem is solved for odd orders v up to 17, and even orders v up to 10 (see also [15, Sections VI.12.4 and VII.5.4]). In [6] the problem is settled whenever v is even, each Fi is bipartite (namely, Fi contains only cycles of even length), a1 > 3 is odd, and the remaining ai are even. In [14, 17] the problem is solved whenever v = pn with p a prime number, t = n, and Fi is a Cpi-factor, except possibly whenp is odd and the first non-zero integer of (a^ a2,..., an) is 1. A partial asymptotic existence result has recently been given in [20], provided that v is sufficiently large and a1 scales linearly with v. Further results covering specific cases can be found in [5, 26, 28].
In this paper, we focus on the "uniform" generalized Oberwolfach problem OPt (v; (Ni); (ai)). In view of Theorem 1.2, for such a problem to be solvable v must be a multiple of each N and |_^J = £i=1 o^; clearly, 1 < t < ^. Since OPt(v; (Ni); (a)) has been solved for t = 1 (Theorem 1.1), from now on we assume that t > 1. Also, we denote by [a, b] the set of integers from a to b inclusive; clearly, [a, b] is empty when a > 6. The main result of this paper is the following.
Theorem 1.3. Let v > 3 be odd, let 3 < Ni < N < • • • < N and set N = lcm(N1, N2,..., Nt) and g = gcd(N1, N2,..., Nt); also, let a1, a2,..., at be positive integers. Then, OPt(v; (Ni); (ai)) has a solution if and only if N is a divisor of v and ai = except possibly when t > 1 and at least one of the following conditions is satisfied:
(I)	ai = 1 for some i G [1,t];
(II)	ai G [2, N-3] U {N+1} for every i G [1, t];
(III)	g = 1;
(IV)	v = N.
Given a graph G, G[n] denotes the lexicographic product of G with the complement of Kn, namely, G[n] is the graph whose vertex set is V(G) x Zn, and two vertices (x, j) and (y, j') are adjacent if and only if x and y are adjacent in G.
The proof of the main theorem relies on the solvability of OPt(Cg[n]; (gni); (ai)). More precisely, we prove the following result.
Theorem 1.4. Let t > 1 and let 1 < n1 < n2 < • • • < nt < n be odd integers such that ni is a divisor of n for each i G [1, t]. Then OPt(Cg [n]; (gni); (ai)) has a solution whenever g > 3, 1=1 ai = n, and ai > 2 for every i G [1, t].
In the next section we introduce some tools and provide some powerful methods which we use in Section 3 where we prove Theorem 1.4. In Section 4 we prove the main results.
2 Preliminary results
We will make use of the notion of a Cayley graph on an additive group r, not necessarily abelian. Given Q C r \ {0}, the Cayley graph Cay(r, Q) is a graph with vertex set
70
ArsMath. Contemp. 17(2019)67-78
r and edge set {y(w + 7) | 7 G r, w g Q}. When r = Zn this graph is known as a circulant graph. We note that the edges generated by w g Q are the same as those generated by —w g —Q, so that Cay(r, Q) = Cay(r, ±Q), and that the degree of each point is |Q U (—Q)|.
Given a subgraph G of Cay(r, Q) and an element 7 g r, we denote by G + 7 the translate of G by 7, that is, the graph obtained from G by replacing each of its vertices, say x, with x + 7. It is not difficult to check that G + 7 is a subgraph of Cay(r, Q). For a subgroup E of r, the orbit of G under E (briefly, the E-orbit of G) is the set Orbs(G) of all distinct translates of G by an element of E, that is, Orbs(G) = {G + a | a g E}. The E-stabilizer of G is the set Stabs(G) of the elements a g E such that G + a = G. By the well-known orbit-stabilizer theorem (see [27, Theorem 5.7]), Stabs(G) is a subgroup of E of index Orbs (G), and therefore | Orbs (G) | • | Stabs (G) | = | E |.
Given a set Q C r, we denote by Cf [Q] (i > 3) the graph with point set Zf x r and edges (j, y)(1 + j, w + 7), with j g Zf, 7 g r and w g Q. In other words, Cf[Q] = Cay(Zf x r, {1} x Q); hence, it is 2|Q|-regular. It is straightforward to see that if r has order n, then Cf[n] = Cf[r]; hence, Cf[Q] is a subgraph of Cf[n]. We call the elements of Q (mixed) differences.
Finally, given a set of cycle factors, C, of Cf[n], and a set Q C r we say that C exactly covers Q, or Cf[Q], if C is a factorization of Cf [Q].
The following result, which generalizes Theorem 2.11 of [13], provides sufficient conditions for the existence of a solution to OPt(Cf [Q]; (in»); (a»)), where Q is a subset of an arbitrary group r of order n and each n is a positive divisor of n.
Theorem 2.1. Let r be an additive group of order n not necessarily abelian, and let 1 < ni < n2 < • • • < nt < n be odd integers such that n is a divisor of n for each i G [1, t]; also, let Q be a subset of r, and let a1, a2,... at be non-negative integers such that Y^t=1 a» = |Q|. If there exists an |Q| x i matrix A with i > 3 and entries in Q satisfying the following properties:
(1)	for each i G [l,t] there are a» rows of A whose right-to-left sum is an element of order n» in r,
(2)	each column of A is a permutation of Q,
then OPt(Cf [Q]; (in»); (a»)) has a solution. Moreover, if we also have that
(3)	Q is closed under taking negatives,
then OPt(Cg [Q]; (gn); (a»)) has a solution for any g > i with g = i (mod 2).
Proof. Let A = [ahk] be an |Q| x i matrix with entries from Q C r and satisfying conditions (1) and (2); also, set a0 = 0, a» = J2j=1 aj and let R = [aj_1 + l, a»] for i G [l, t]. Note that the Rs partition the interval [l, |Q|] since by assumption at = Xj=1 aj = |Q|. By condition (1) and reordering rows if necessary, we can index the rows of A whose right-to-left sum is an element of order n by the elements of R. Thus, we may assume that the right-to-left sum of the h-th row of A is an element of order n if and only if h G R.
For l < h < |Q| and l < k < i, set Sh,o =0 and sh,k = ah,k + ah,k_1 +-----+ afe,1.
Note that sh,f is the right-to-left sum of the h-th row of A and, by the above, sh,f has order n if and only if h G R; in this case, nsh,f = 0 and psh,f = 0 for any p G [l, n — l]. Therefore, for each i G [l, t] and h G R, the following in»-cycle is well defined:
A. C. Burgess et al.: On the generalized Oberwolfach problem
71
C h
(c
h ch
0, c1,
cJtf-1), where ch

(u, Shu + Msh,i), for
e [0,i - 1], m e [0,n - 1].
We start by showing that Orbp(Ch), where r = {0} x r, is a Cnif-factor of Cf[n]. First, note that Ch + (0, sh,f) = Ch; in fact, c^ + (0, sh,f) = for each w e [0, n,i - 1], where the subscript w + i is taken modulo nji. In other words, addition by (0, sh,f) is equivalent to a rotation of Ch by i. This means that (0, sh,f) lies in Stabp(Ch). Since the order of (0, sh,f) coincides with the order of sh,f, which by assumption is n,, we have that | Stabr(Ch)| > n,. Therefore,	'
| Orbr(Ch)| = |f|/| Stabr(Ch)| < n/n,.
Hence, Orbp(Ch) contains at most n/n, C„.f-cycles. To show that Orbp(Ch) is actually a Cnit-factor of Cf [n], it is then enough to check that it contains all vertices of Cf [n] at least once. Given the point (u, z) e Zf x r, we have that z = sh,u + xu, for a suitable xu e r. Therefore, (u, z) = cU + (0, xu); hence, (u, z) is a vertex of Ch + (0, xu) e Orbp(Ch).
We claim that F =u {Orbr(Ch) | h = 1, 2,..., |Q|} is a 2-factorization of Cf[Q]. Note that the factors of F contain between them at most in|Q| = |E(Cf [Q])| edges, counted with their multiplicity. Therefore, it is enough to show that every edge of Cf [Q] lies in some translate of Ch, for a suitable h. First recall that each edge of Cf [Q] has the form (u, x)(1 + u, w + x) for some (u, x) e Zf x r and w e Q. Since, by assumption, any column of A = [ahfc] is a permutation of Q, there is an integer h such that ah,u+1 = w. Note that (u, Sh,u)(1 + u, Sh,u+i) e E(Ch) and Sh,u+i - Sh,u = «h,u+i = w. Therefore, (u, x)(1 + u, w + x) is an edge of Ch + (0, -sh,u + x) and the assertion follows.
In order to prove the second part, let g = i + 2q, Q = {w1, w2,..., w^ }, and let A' be the |Q| x 2q matrix defined below:
A' =
w1 - w1 w2 - w2
w1 - w1 w2 - w2
wl m

w|m|
wl m

w|m|.
Since Q = -Q (condition (3)), it is easy to check that the matrix [A A'] is an |Q| x g matrix satisfying conditions (1) - (2), and this completes the proof.	□
We point out that while the above theorem is proved for an arbitrary group r, in this paper it is always used when r = Zn. Also, note that if t = 1, then Theorem 2.1 constructs a Cfni -factorization of Cf [T] or a Cgni -factorization of Cg [T].
The following corollary is a straightforward consequence of the above theorem by taking q = r = zn.
Corollary 2.2. Let t > 1 and let 1 < n1 < n2 < • • • < nt < n be odd integers such that n, is a divisor of n for any i e [1, t]; also, let a1, a2,..., at be non-negative integers such thatJ2i=1 a, = n. If there exists an n x i matrix A with i > 3 and entries from Zn satisfying the following properties:
(1)	for each i e [1, t], A has a, rows each of which sums to an element of order n, in Zn,
(2)	each column of A is a permutation of Zn,
u
72
ArsMath. Contemp. 17(2019)67-78
then OPi(Cg [n]; (gn^; (a^)) has a solution for any g > £ with g = £ (mod 2).
We end this section by recalling the following result proven in [21] which is here stated in a slightly different, but equivalent, form.
Lemma 2.3 ([21]). Let r = {71,72,..., Yn} be an additive abelian group of order n, and let J1, S2,..., Sn be elements of r, not necessarily distinct, such that Y^"=1 Si = 0. Then there exist a permutation ^ of r and a permutation n of the interval [1, n] such that ^(7i) - Yi = ^n(i) for every i e [1,n].
3 Solving OPt(Cg[n]; (gni); (ai))
In this section, by exploiting our preliminary results, we provide sufficient conditions for
OPt(Cg [n]; (gni); (ai)) to be solvable.
Theorem 1.4. Let t > 1 and let 1 < n1 < n2 < • • • < nt < n be odd integers such that ni is a divisor of n for each i e [1, t]. Then OPt(Cs [n]; (gni); (ai)) has a solution whenever g > 3, ^i=1 ai = n, and ai > 2 for every i e [1, t].
Proof. Let ai > 2 for i e [1,t] be integers such that J2i=1 a = n. Also, let A = {¿1, S2,..., Sn} be the list of elements of Zn defined as follows: set so = 0, si = Y^j=1 aj for every i e [1, t], and let
___n
, ,...,, ,	if ai is even,
(SSi_1 + 1,SSi_1+2,...,SSi) =
' nn, - n,..., n, -IL,IL, nn, -	if ai is odd,
ni ' ni ' ' ni' ni' ni' ni' ni '	''	1
for every i e [1, t]. By recalling that n is odd, we have that SSi_1+1, SSi_1+2,..., Ssi are all elements of Zn of order ni, and they sum to 0. It follows that the elements of A sum to 0, and Lemma 2.3 guarantees the existence of two permutations ^ and n of Zn such that *(i) - i = Sn(i) for every i e Zn.
Now for each £ e {3,4}, let A£ be the n x £ matrix whose i-th row is either
[^(i) - 2 - i] or [^(i) i -i -i]
according to whether £ = 3, or 4, respectively. It is not difficult to check that A3 and A4 satisfy the following conditions:
(i)	for each i e [1, t], A3 (resp., A4) has ai rows each of which sums to an element of order ni,
(ii)	each column of A3 (resp., A4) is a permutation of Zn.
In other words, A3 and A4 satisfy the assumptions of Corollary 2.2 which guarantees the solvability of OPt(Cg[n]; (gni); (ai)) whenever g > 3.	□
We point out that Theorem 1.4 holds also when g = 2. In this case, C2[n] is taken to be the complete bipartite graph with parts of size n whose edges are taken with multiplicity two. This can be seen by following the proof of Theorem 1.4 but using the matrix
[*(i) -i].
3
a
A. C. Burgess et al.: On the generalized Oberwolfach problem
73
4 Solving OPf(v;(Ni);(ai))
We say that OPt(G; (N»); (a»)) and OP„(G; (Mj); (Pj)) are equivalent if =x a» = J2m- =x Pj for any x > 3. For example, OP4(G;4,4, 5,7; 4, 6, 8, 2) is equivalent to op/(G;4,4, 4, 5, 7; 2, 3, 5, 8, 2).
Moreover, for any non-negative integer a we define the integer f (a) as follows:
a — p
f (a) = —, where {0, 2, 4} 3 p = a (mod 3).
Clearly, a = 3f (a) + p and f (a) = a (mod 2).
The following result provides sufficient conditions for the existence of a solution to OPt(G; (gn»); (a»)) for an arbitrary graph G.
Theorem 4.1. Let t > 2, and let 1 < ni < n2 < • • • < nt < n be odd integers such that n» is a divisor of n for each i G [1, t]. Also, let G be a graph having a factorization into r Cg[n]-factors with g > 3. Then, OPt(G; (gn»); (a,)) has a solution whenever the following conditions simultaneously hold:
(!) Ei=1 a» = rn;
(2)	0 < a» = 1 for every i G [1, t];
(3)	Et=i f (a») > r;
(4)	|{i G [1,t] | a» is odd}| < r (2[2-2J + 1).
Proof. Let n = 6q+p where p G {3, 5, 7} and let F = {F1, F2,..., Fr } be a factorization of G into r Cg [n]-factors. We proceed by induction on r. If r = 1, the assertion follows from Theorem 1.4. Now, let r > 2 and assume that the assertion holds for any graph having a factorization into r - 1 Cg [n]-factors. It is enough to show that OPt(G; (gn»); (a»)) is equivalent to a problem of the following form:
OP„(G;(Nj);(Pj)), where j G {2,3} and
r < S = |{j G [1,u] | Pj = 3}| < r(2q + 1). ( . )
In fact, assuming this equivalence, we only need define Pjs so that OPu(F1; (Nj); (Pj)) and OPu(G - F1; (Nj); (Pj - Pj)) are solvable; it follows that the problem in (4.1), and hence, the original problem has a solution. We first assume (without loss of generality) that Pj = 3 if and only if j G [1, S] and consider the following two cases:
1. if S G [r, r + 2q], set
J, = i Pj if j G {1} U [S +1,S + ]; j 0 otherwise;
2. if S G [r + 2q + 1, r(2q + 1)], we define Pj as follows,
f Pj if j = [1, 2q + 1] U [S +1,S + £-3]; j 0 otherwise.
74
ArsMath. Contemp. 17(2019)67-78
By Theorem 1.4, there exists a solution to OPu(Fi; (Nj); )). It is not difficult to check that OPu(G - F1; (Nj); (£j - )) satisfies all the assumption of this theorem, therefore, by the induction hypothesis, it is solvable.
We now show that OPt(G; (gn»); (a»)) is equivalent to a problem of the form (4.1). We reorder the a»s so that the even a»s appear first. For every i e [1, t] we define the quadruple of integers (72®-1,72», N2i-1, N2i) as follows:
{(a» - 3, 3) if a» is odd; (72i-i,72i) = < ,	.	N2i-1 = N2i = gn».
I (a», 0) if a» is even;
It follows that y1, y2 ,..., 72t-d are even, whereas 7» = 3 for any i e [2t - d +1,2t], where d = |{i e [1,t] | a» isodd}| is the number of odd a»s. We point out that OP t(G; (gn»); (a»)) is equivalent to OP2«(G; (N»); (7®)); also, since by assumption E«=i f (a») > r, it follows that £2= 1 f (y») > r.
We first assume that d < r. Now, let k e [1,2t - d] be the greatest integer such that f (y») > r, and set r' = J2i=k+i. f (y»). Clearly, r' < r; also, r - r' is even, since:
k 2t 2t 2t r = rn = y» + 53 Y» =	Y»	f (y») = r' (mod 2).
»=1 »=k+1 »=k+1 »=k+1
We proceed by defining a suitable partition (y»1, y»2 ,..., Y»,«* ) of the integer y» such that
Y»j e {0,2, 3}. First, for each i e [k, 2t] set (q», p») = (f (y»), Y» - 3f (y»)) and note that p» e {0, 2,4}. Recall now that Yk = 3qk + pk is even, hence qk is even; also, r - r' is even and qk > r - r'. Therefore, Yk = 3(r - r') + 2y where y = 3(qk-r+r )+Pfc. We now define a partition (y»1, Y»2,..., Y»,«*) of Y» as follows:
if i e [1, k - 1], set t» = y»/2 and Y»j = 2 for any j e [1, t»]; if i = k, set t» = r - r' + y and Y»j : if i e [k +1, 2t], set t» = q» + 2 and
3 if j e [1, r - r']; 2 otherwise.
3 if j e [1, q»]; Y»j H0 if (j,p») e{(q» + 1, 0), (q» + 2, 0), (q» + 2, 2)}; 2 otherwise.
Finally, for any i e [1, 2t] and j e [1, t»] set N»j = N» and u = J21= 1t». Clearly, the original problem OP2«(G; (N»); (y»)) is equivalent to OP„(G; (N»j); (y^)) where Y»j e {0, 2,3} and there are exactly r Y»js equal to 3. By removing all pairs (N»j, Y»j) with Y»j = 0, we obtain a problem of the form (4.1).
We finally consider the case where d > r. As before, we define a partition (y»i, Y»2,..., Y»,ti) of the integer y» as follows:
(t ) [(?, 2) if i e [1,2t - d] and j e [1, f ];
(»,Y»j) 1(1,3) otherwise;
A. C. Burgess et al.: On the generalized Oberwolfach problem
75
and set Nj = N for any j e [Mi], and u = J21*= 1 Clearly, the original problem
OPi*(G; (Nj); (7i)) is equivalent to OP„(G; (Nj); (j)) where Yj e {2,3} and there are exactly dYj s equal to 3. Since, d < r(2q+1) by assumption, then OPu(G; (Nj ); (Yj )) is of the form (4.1), and this completes the proof.	□
We now provide a result for the complete equipartite graph.
Theorem 4.2. Let s, w > 3 be odd integers, let 3 < N1 < N2 < • • • < Nt, and let a1, a2,..., a* be positive integers. IfJ2*(1 ai = (s-21)w and each N is a divisor of w, then OP*(Ks[w]; (Ni); (ai)) is solvable, except possibly when t > 1 and at least one of the following conditions is satisfied:
(A)	ai = 1 for some i e [1,t];
(B)	gcd(N1,Ni,...,Nt) = 1.
Proof. We assume that t > 2, since the case t = 1 is solved in Theorem 1.1.
Now, set N = lcm(N1, Ni,..., N*) and g = gcd(N1, Ni,..., N*); also, let n = Ni/g, set n = lcm(n1, n2,..., nt) and note that N = gn. By assumption, we have that each Ni is a divisor of w, that is, N is a divisor of w, hence w = gnw for some integer w > 0. By Theorem 1.1, there exists a Cg -factorization of Ks[gw] with r Cg-factors, where r = gw(s - 1)/2. By expanding each vertex of this factorization by n, we get a Cg [n]-factorization F of Ks [gw][n] = Ks [w] with r Cg [n]-factors.
We first assume that n > 7. In this case, to solve OPt(Ks [w]; (Ni); (ai)) it is enough to show that conditions (1)-(4) of Theorem 4.1 are satisfied. By assumption J2¿(1 ai = (s-21)w = rn, and by exception (A) we have that ai > 2 for every i e [1, t]. Further,
r2
n — 2 \ r(n — 4) gw(s — 1) . .	n
+ 1 > ^-= ^-(n - 4) > n - 4 > -,
y	3	6	3
and since n hasatmost [n^J distinct divisors, we have that n > t, hence r (2 L^-^] + 1) > t. Finally, we have that
t t t t rn = Y, ai < ^(3/(aj) + 4) = 4t + 3 ^ f (aj) < 4r + 3 ^ f (aj),
i=1 j=1 j=1 j=1
and since n > 7, it follows that J2¿(1 f (aj) > r(n - 4)/3 > r. Therefore, all conditions ofTheorem4.1 are satisfied, hence OP*(Ks[w]; (Nj); (aj)) is solvable.
It is left to consider the cases where n e {3,5}. Since Nj is a multiple of g and a divisor of gn, then Nj e {g, gn} for any i. By recalling that N1 < N2 < • • • < N* and t > 2, we have that t = 2 and (N1, N2) = (g, gn). Now, let a2 = xn + y where x > 0 and y e [0, n - 1], and since a2 > 2 (exception (A)), then (x, y) = (0,1). If y =1, we apply Theorem 1.4 to fill x Cg[n]-factors of F with a solution of OP2(Cg[n]; g, gn; 0, n), one Cg[n]-factor with a solution of OP2(Cg[n]; g, gn; n - y, y), and the remaining r - x - 1 factors of F with a solution of OP2(Cg [n]; g, gn; n, 0). Similarly, if y =1, since x > 0 and r > g > 3 (exception (B)), we again apply Theorem 1.4 and fill x - 1 Cg [n]-factors of F with a solution of OP2(Cg[n]; g, gn;0,n), one Cg[n]-factor with a solution of OP2(Cg[n]; g, gn; 1, n - 1), one Cg [n]-factor with a solution of OP2(Cg[n]; g, gn;
n-2, 2), and the remaining r-x-1 factors of F with a solution of OP2(Cg [n]; g, gn; n, 0).
□
76
ArsMath. Contemp. 17(2019)67-78
We are now ready to prove the main result of this paper.
Theorem 1.3. Let v > 3 be odd, let 3 < N1 < N2 < ■■■ < Nt and set N = lcm(Ni, N2,..., Nt) and g = gcd(Ni, N2,..., Nt); also, let ai, a2,..., at be positive integers. Then, OPt(v; (Nj); (a^) has a solution if and only if N is a divisor of v and aj = v-22i except possibly when t > 1 and at least one of the following conditions is satisfied:
(I) aj = 1 for some i G [1, t]; (II) aj G [2, N-3] U { N+1} for every i G [1, t];
(III)	g = 1;
(IV)	v = N.
Proof. By Theorem 1.2, if OPt(v; (Nj); (aj)) has a solution, then N is a divisor of v and aj = . We now show sufficiency and assume that t > 2, since the case t =1 is solved in Theorem 1.1. Let v = Ns for a suitable odd integer s. By exception (IV), we have that s > 3.
We first factorize Kv into G0 = sKN and G1 = Ks [N]. By exception (II), there exists k G [1, t] such that either ak = N-1 or aj > N+3. Then, we apply Theorem 1.1 to fill G0 with a CNk-factorization. It remains to solve OPt(G1; (Nj); (aj)) where aj = aj -if i = k, and aj = aj otherwise. By taking into account exceptions (I) and (III), we have that:
(a)	aj =1 for any i G [1, t], and
(b)	g > 3.
Therefore, Theorem 4.2 guarantees the solvability of OPt (G1 ; (Nj); (aj)) and the assertion is proven.	□
Corollary 4.3. Let v > 3 be odd, let 3 < N1 < N2 < ■ ■ ■ < Nt, set N = lcm(N1, N2,..., Nt), and let a1, a2,... ,at be positive integers. Then, OPt(v; (Nj); (aj)) has a solution whenever N is a divisor of v,J2i=1 aj = , and the following conditions are satisfied:
(1)	aj = 1 for any i G [1,t];
(2)	gcd(N1, N2,..., Nt) > 3;
(3)	v > (t + 1)N.
Proof. The case t = 1 is solved in Theorem 1.1, therefore, we let t > 2. By condition (3) and considering that J2i=1 aj = v—r, it follows that there exists k G [1, t] such that ak > N+3. If we also take into account conditions (1) and (2), we have that all assumptions of Theorem 1.3 are satisfied, and the assertion follows.	□
5 Conclusions
This paper deals with the generalized Oberwolfach problem, denoted by OPt(v; N1, N2, ..., Nt; a1, a2,..., at), which asks for a 2-factorization of the complete graph Kv into aj copies of a CNi-factor, for i G {1, 2,..., t}. For a solution of this problem to exist, v must be odd, each Nj must be a divisor of v, and J2j aj = (Theorem 1.2).
A. C. Burgess et al.: On the generalized Oberwolfach problem
77
This problem has been widely studied when t = 1 or 2. The case t = 1 represents the 'uniform' Oberwolfach problem which has been solved in 1989 [3]. When t = 2, this problem is known as the Hamilton-Waterloo problem. Although this version of the problem is still open, by using techniques similar to those adopted in this paper, the current authors were able to make significant progress in the challenging case where the cycle lengths are odd [12, 13].
This paper makes significant progress (Theorem 1.3) on the generalized Oberwolfach problem by showing that the above necessary conditions suffice whenever v > (t + 1)N, each a is greater than 1, and g > 3, where g = gcd(Ni, N2,..., Nt) (Corollary 4.3). This result and its stronger version (Theorem 1.3) rely on Theorem 1.4 which concerns the existence of a factorization of Cg[n] into a Cgni-factors for i e {1, 2,... ,t} (that is, the generalized Oberwolfach problem over Cg [n]). Theorem 1.4 shows that the trivial necessary conditions suffice whenever g > 3, and a > 1 for each i. Clearly, removing this last condition from Theorem 1.4 would automatically yield a similar improvement of our main theorem.
More generally, we provide sufficient conditions (Theorem 4.1) for the solvability of the generalized Oberwolfach problem over an arbitrary graph G. As a consequence, we provide, with Theorem 4.2, a result for the complete equipartite graph, similar to those mentioned above.
References
[1]	P. Adams and D. Bryant, Two-factorisations of complete graphs of orders fifteen and seventeen, Australas. J. Combin. 35 (2006), 113-118, https://ajc.maths.uq.edu.au/ pdf/35/ajc_v35_p113.pdf.
[2]	B. Alspach and R. Haggkvist, Some observations on the Oberwolfach problem, J. Graph Theory 9 (1985), 177-187, doi:10.1002/jgt.3190090114.
[3]	B. Alspach, P. J. Schellenberg, D. R. Stinson and D. Wagner, The Oberwolfach problem and factors of uniform odd length cycles, J. Comb. Theory Ser. A 52 (1989), 20-43, doi:10.1016/ 0097-3165(89)90059-9.
[4]	J. Asplund, D. Kamin, M. Keranen, A. Pastine and S. Ozkan, On the Hamilton-Waterloo problem with triangle factors and C3x-factors, Australas. J. Combin. 64 (2016), 458-474, https://ajc.maths.uq.edu.au/pdf/64/ajc_v64_p458.pdf.
[5]	D. Bryant, Hamilton cycle rich two-factorizations of complete graphs, J. Combin. Des. 12 (2004), 147-155, doi:10.1002/jcd.20005.
[6]	D. Bryant and P. Danziger, On bipartite 2-factorizations of Kn — I and the Oberwolfach problem, J. Graph Theory 68 (2011), 22-37, doi:10.1002/jgt.20538.
[7]	D. Bryant, P. Danziger and M. Dean, On the Hamilton-Waterloo problem for bipartite 2-factors, J. Combin. Des. 21 (2013), 60-80, doi:10.1002/jcd.21312.
[8]	D. Bryant, P. Danziger and W. Pettersson, Bipartite 2-factorizations of complete multipartite graphs, J. Graph Theory 78 (2015), 287-294, doi:10.1002/jgt.21806.
[9]	D. Bryant and V. Scharaschkin, Complete solutions to the Oberwolfach problem for an infinite set of orders, J. Comb. Theory Ser. B 99 (2009), 904-918, doi:10.1016/j.jctb.2009.03.003.
[10]	M. Buratti and P. Danziger, A cyclic solution for an infinite class of Hamilton-Waterloo problems, Graphs Combin. 32 (2016), 521-531, doi:10.1007/s00373-015-1582-x.
[11]	M. Buratti and T. Traetta, 2-starters, graceful labelings, and a doubling construction for the Oberwolfach problem, J. Combin. Des. 20 (2012), 483-503, doi:10.1002/jcd.21296.
104
ArsMath. Contemp. 17 (2019) 78-114
[12]	A. C. Burgess, P. Danziger and T. Traetta, On the Hamilton-Waterloo problem with odd orders, J. Combin. Des. 25 (2017), 258-287, doi:10.1002/jcd.21552.
[13]	A. C. Burgess, P. Danziger and T. Traetta, On the Hamilton-Waterloo problem with odd cycle lengths, J. Combin. Des. 26 (2018), 51-83, doi:10.1002/jcd.21586.
[14]	N. J. Cavenagh, S. I. El-Zanati, A. Khodkar and C. Vanden Eynden, On a generalization of the Oberwolfach problem, J. Comb. Theory Ser. A 106 (2004), 255-275, doi:10.1016/j.jcta.2004. 02.003.
[15]	C. J. Colbourn and J. H. Dinitz (eds.), The CRC Handbook of Combinatorial Designs, CRC Press Series on Discrete Mathematics and its Applications, CRC Press, Boca Raton, Florida, 1996, doi:10.1201/9781420049954.
[16]	J. H. Dinitz and A. C. H. Ling, The Hamilton-Waterloo problem: the case of triangle-factors and one Hamilton cycle, J. Combin. Des. 17 (2009), 160-176, doi:10.1002/jcd.20196.
[17]	S. I. El-Zanati, S. K. Tipnis and C. Vanden Eynden, A generalization of the Oberwolfach problem, J. Graph Theory 41 (2002), 151-161, doi:10.1002/jgt.10058.
[18]	F. Franek, J. Holub and A. Rosa, Two-factorizations of small complete graphs. II. The case of 13 vertices, J. Combin. Math. Combin. Comput. 51 (2004), 89-94.
[19]	F. Franek and A. Rosa, Two-factorizations of small complete graphs, J. Statist. Plann. Inference 86 (2000), 435-442, doi:10.1016/s0378-3758(99)00123-8.
[20]	S. Glock, F. Joos, J. Kim, D. Kuhn and D. Osthus, Resolution of the Oberwolfach problem, arXiv:1806.04644 [math.CO].
[21]	M. Hall, Jr., A combinatorial problem on abelian groups, Proc. Amer. Math. Soc. 3 (1952), 584-587, doi:10.2307/2032592.
[22]	D. G. Hoffman and P. J. Schellenberg, The existence of Ck -factorizations of K2n — F, Discrete Math. 97 (1991), 243-250, doi:10.1016/0012-365x(91)90440-d.
[23]	M. S. Keranen and A. Pastine, A generalization of the Hamilton-Waterloo problem on complete equipartite graphs, J. Combin. Des. 25 (2017), 431-468, doi:10.1002/jcd.21560.
[24]	J. Liu, The equipartite Oberwolfach problem with uniform tables, J. Comb. Theory Ser. A 101 (2003), 20-34, doi:10.1016/s0097-3165(02)00011-0.
[25]	F. Merola and T. Traetta, Infinitely many cyclic solutions to the Hamilton-Waterloo problem with odd length cycles, Discrete Math. 339 (2016), 2267-2283, doi:10.1016/j.disc.2016.03. 026.
[26]	U. Odaba§i and S. Ozkan, Uniformly resolvable cycle decompositions with four different factors, Graphs Combin. 33 (2017), 1591-1606, doi:10.1007/s00373-017-1856-6.
[27]	H. E. Rose, A Course on Finite Groups, Universitext, Springer-Verlag, London, 2009, doi: 10.1007/978-1-84882-889-6.
[28]	B. Stevens, The anti-Oberwolfach solution: pancyclic 2-factorizations of complete graphs, Theoret. Comput. Sci. 297 (2003), 399-424, doi:10.1016/s0304-3975(02)00650-3.
[29]	T. Traetta, A complete solution to the two-table Oberwolfach problems, J. Comb. Theory Ser. A 120 (2013), 984-997, doi:10.1016/j.jcta.2013.01.003.