ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 11 (2016) 157-173
On factorisations of complete graphs into circulant graphs and the Oberwolfach problem
Brian Alspach
School of Mathematical and Physical Sciences, University of Newcastle, Callaghan, NSW 2308, Australia.
Darryn Bryant
School of Mathematics and Physics, The University of Queensland, Qld 4072, Australia.
Daniel Horsley
School of Mathematical Sciences, Monash University, Vic 3800, Australia.
Barbara Maenhaut, Victor Scharaschkin
School of Mathematics and Physics, The University of Queensland, Qld 4072, Australia.
Received 21 November 2014, accepted 5 August 2015, published online 3 October 2015
Various results on factorisations of complete graphs into circulant graphs and on 2-factorisations of these circulant graphs are proved. As a consequence, a number of new results on the Oberwolfach Problem are obtained. For example, a complete solution to the Oberwolfach Problem is given for every 2-regular graph of order 2p where p = 5 (mod 8) is prime.
Keywords: Oberwolfach problem, graph factorisations, graph decompositions, 2-factorisations. Math. Subj. Class.: 05C70, 05C51, 05B30
E-mail addresses: brian.alspach@newcastle.edu.au (Brian Alspach), db@maths.uq.edu.au (Darryn Bryant), danhorsley@gmail.com (Daniel Horsley), bmm@maths.uq.edu.au (Barbara Maenhaut), victors@maths.uq.edu.au (Victor Scharaschkin)
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
Abstract
158
Ars Math. Contemp. 11 (2016) 101-106
1 Introduction
The Oberwolfach problem was posed by Ringel in the 1960s and is first mentioned in [16]. It concerns graph factorisations. A factor of a graph is a spanning subgraph and a factorisation is a decomposition into edge-disjoint factors. A factor that is regular of degree k is called a k-factor. If each factor of a factorisation is a k-factor, then the factorisation is called a k-factorisation, and if each factor is isomorphic to a given graph F, then we say it is a factorisation into F.
Let F be an arbitrary 2-regular graph and let n be the order of F. If n is odd, then the Oberwolfach Problem OP(F) asks for a 2-factorisation of Kn into F, and if n is even, then OP(F) asks for a 2-factorisation of Kn - I into F, where Kn - I denotes the graph obtained from Kn by removing the edges of a 1-factor.
The Oberwolfach Problem has been solved completely when F consists of isomorphic components [1, 3,18], when F has exactly two components [29], when F is bipartite [5,17] and in numerous special cases. See [7] for a survey of results up to 2006. It is known that there is no solution to OP(F) for F G {C3 UC3, C4 UC5, C3 UC3 UC5, C3 UC3 UC3 UC3}, but a solution exists for every other 2-regular graph of order at most 40 [13].
In [8], it was shown that the Oberwolfach Problem has a solution for every 2-regular graph of order 2p where p is any of the infinitely many primes congruent to 5 (mod 24), and for every 2-regular graph whose order is in an infinite family of primes congruent to 1 (mod 16). In this paper we extend these results as follows. We show that OP(F) has a solution for every 2-regular graph of order 2p where p is any prime congruent to 5 (mod 8) (see Theorem 4.2), and we obtain solutions to OP(F) for broad classes of 2-regular graphs in many other cases (see Theorems 4.3 and 4.4). We also obtain results on the generalisation of the Oberwolfach Problem to factorisations of complete multigraphs into isomorphic 2-factors (see Theorem 5.4). Our results are obtained by constructing various factorisations of complete graphs into circulant graphs in Section 2, and then showing in Section 3 that these circulant graphs can themselves be factored into isomorphic 2-regular graphs in a wide variety of cases.
2 Factorising complete graphs into circulant graphs
Let G = (G, •) be a finite group with identity e and let S be a subset of G such that e G S and s G S implies s-1 G S. The Cayley graph on G with connection set S, denoted Cay(G ; S), has the elements of G as its vertices and g is adjacent to g • s for each s G S and each g g G. A Cayley graph on a cyclic group is called a circulant graph. We use the following standard notation. The ring of integers modulo n is denoted by Zn, the multiplicative group of units modulo n is denoted by Z*n and, when b divides |Z^|, the subgroup {xb : x G Z*n} of index b in Zn is denoted by (Zn)b.
In this section we consider factorisations of Kn for n odd (in Section 2.1) and of Kn -I for n even (in Section 2.2) into circulant graphs. A 2-regular graph is a circulant if and only if its components are all isomorphic. Thus, for each 2-regular circulant graph F, there exists a factorisation of Kn (if F has odd order) or of Kn - I (if F has even order) into F ; except that there is no such factorisation when F G {C3 U C3, C3 U C3 U C3 U C3}. Considerably less is known for factorisations into circulant graphs of degree greater than 2. Some factorisations into Cay(Zn ; ±{1, 2}) and Cay(Zn ; ±{1, 2, 3,4}) are given in [4] and [8] respectively, and some further results, including results on self-complementary and almost self-complementary circulant graphs, appear in [2, 14, 15, 26].
B. Alspach et al.: On factorisations of complete graphs into circulant graphs and... 159
2.1 Factorising complete graphs of odd order
In this subsection we will construct factorisations of complete graphs of odd order into isomorphic circulant graphs by finding certain partitions of cyclic groups. Problems concerning such partitions have been well studied, for example see [28], and existing results overlap with some of the results in this subsection. In particular, Theorem 2.3 below is a consequence of Lemma 3.1 of [24].
Lemma 2.1. Let s be an integer, let p = 1 (mod 2s) be prime, and let S = ±{di, d2,..., ds} Ç Zp. Further, suppose a and b are integers such that 2abs = p — 1, let G = (Zp)b, and let H = (Zp)bs. If di, d,2,...,d,s represent the s distinct cosets of G/H, then there exists a 2s-factorisation of Kp into Cay(Zp ; S).
Proof. For each x G Zp let xS = {xy : y G S}. Since p is prime, Cay(Zp ; xS) = Cay(Zp ; S) for any x G Zp \ {0}. If there is a partition of Zp into sets x1S, x2S,..., xabS where xj G Zp \ {0} for i = 1,2,..., ab, then {Cay(Zp ; xjS) : i = 1, 2,..., ab} is the required 2s-factorisation of Kp. We now present such a partition.
Let w be a generator of Zp. Thus, H = w0, wbs, w2bs,..., w(2a-1)bs, and wabs = —1 G H. Let A = w0,wbs,w2bs,.. . ,w(a-1)bs, so that H = A U-A (A is a set of representatives for the cosets in H of the order 2 subgroup of H). Since d1,d2,... ,ds represent distinct cosets of G/H, it is easy to see that {xS : x G A} is a partition of G. Thus, if B is a set of representatives for the cosets of Zp/G, then {xyS : x G A, y G B} is the required partition of Zp.	□
Note that upon putting s = 1 in Lemma 2.1 we obtain the Hamilton decomposition
{Cay(Zp ; {±1}), Cay(Zp ; {±2}),..., Cay(Zp ; {±^})}
of Kp. We will be mostly interested in applications of Lemma 2.1 where the connection set S is ±{1, 2}, ±{1,2,3}, ±{1,3,4} or ±{1, 2, 3,4}. The factorisations given by Lemma 2.1 have the property that each factor is invariant under the action of Zp. It is worth mentioning that for S G {±{1,2}, ±{1, 2, 3}, ±{1,3,4}, ±{1,2, 3,4}}, the construction given in Lemma 2.1 yields every 2s-factorisation of Kp into Cay(Zp ; S) with this property. This follows from the results in [9] and [22], together with Turner's result [30] that for p prime Cay(Zp ; S) = Cay(Zp ; S') if and only if there exists an a G Zp such that S ' = aS.
Theorem 2.2. Ifp = 1 (mod 4) is prime and 4 divides the order of k in Zp, then there is a factorisation of Kp into Cay(Zp ; ±{1, k}).
Proof. Apply Lemma 2.1 with S = ±{1, k} taking G to be the subgroup of Zp generated by k, and H to be the index 2 subgroup of G.	□
Theorem 2.3. Ifp = 1 (mod 6) is prime such that 2,3 G (Zp)3 and 6 G (Zp)3, then there is a factorisation of Kp into Cay(Zp ; ±{1, 2,3}).
Proof. It follows from 2,3 G (Zp)3 and 6 G (Zp)3 that 1, 2 and 3 represent the three cosets of Zp/(Zp)3. Thus, we obtain the required factorisation by applying Lemma 2.1 with b = 1.	□
Theorem 2.4. If p = 1 (mod 6) is prime such that 2,3,6 G (Zp)3, then there is a factorisation of Kp into Cay(Zp ; ±{1, 3,4}).
160
Ars Math. Contemp. 11 (2016) 101-106
Proof. It follows from 2, 3,6 £ (Zp)3 that 1, 3 and 4 represent the three cosets of Z;/(Zp3. Thus, we obtain the required factorisation by applying Lemma 2.1 with b =1.	□
The primes less than 1000 to which Theorem 2.3 applies are
7, 37,139,163,181, 241, 313, 337, 349, 379,409,421, 541, 571, 607, 631, 751, 859, 877, 937, and the primes less than 1000 to which Theorem 2.4 applies are
13,19, 79, 97,199, 211, 331, 373,463,487, 673, 709, 769, 823, 829, 883, 907.
In the next theorem we show that there are infinitely many primes to which Theorem 2.3 applies, and also infinitely many primes to which Theorem 2.4 applies.
Theorem 2.5. There are infinitely many values of p such that p is prime, p = 1 (mod 6), 2,3 £ (Z*)3 and 6 £ (Zp)3, and there are infinitely many values ofp such that p is prime, p = 1 (mod 6) and 2,3,6 £ (Z*)3.
Proof. Assume p = 1 (mod 6). Let Fp be the field with p elements. We use standard definitions and results from algebraic number theory, as found in [20]. The result essentially follows from the Chebotarev Density Theorem.
Let w be a primitive cube root of unity, A = be a cube root of 2 and p = a cube root of 3. Consider the following tower of fields:
M = Q(w, A,p) D L = Q(w,A) D K = Q(w) D Q.
Let OK, OL denote the rings of integers of K and L respectively. We may ignore the finitely many ramified primes. Thus let p be a prime number, sufficiently large that it is unramified in M, let p be a prime in K extending p and p a prime in L extending p. Let K = OK/p and L = OL/p be the residue fields. We view K as embedded in L via the map x + p ^ x + p. As p = 1 (mod 6), p splits in K and K = OK/p ~ Fp.
Since M and L are splitting fields, M/K and L/K are Galois extensions. The Galois group of M/K is Gal (M/K) ~ Z3 x Z3 generated by the maps a: A ^ Aw and ft: p ^ pw. The Frobenius map of L/K is the map x ^ x|L|. The Frobenius element aL is the element of Gal(L/K) inducing the Frobenius map on L/K. (A priori aL could also depend on the choice of p extending p, but this is not the case since Gal(L/K) is abelian; see [20, IIL2.1].) Define af £ Gal(M/K) analogously. Then aL is the restriction of a^ to L by [20, m.2.3].
By definition of L, for all sufficiently large p = 1 (mod 6), 2 £ (Z*)3 if and only if L = K. But L = K if and only if aL is the identity map, and it follows that 2 £ (Z*)3 if and only if £ (ft). Similarly, 3 £ (Z*)3 if and only if aM £ (a) and 6 £ (Zp)3 if and only if aM £ (aft). In summary:
2, 3 £ (Z*)3, 6 £ (Z*)3 ^ apM £ {aft, a2ft2}. 2, 3,6 £ (Zp)3	^ af £{a2ft,aft2}.
The Chebotarev Density Theorem [20, V.10.4] implies that for each d £ Gal(M/K), the set of primes p of K (unramified in M) for which af = 0 is infinite. Thus each of the two conditions for af displayed above holds infinitely often.	□
It is possible to describe the primes in Theorem 2.5 more explicitly. Given p = 1 (mod 6), factoring the ideal pOK and taking norms, one shows there exist unique c, d £
B. Alspach et al.: On factorisations of complete graphs into circulant graphs and... 161
Z with d > 0, gcd(c, d) = 1, c = 2 (mod 3) and 4p = (2c - 3d)2 + 27d2. Let t(p) = (c (mod 6), d (mod 6)). There are 9 possible values for t(p): (2,1), (2, 3), (2, 5), (5,0), (5,1), (5,2), (5,3), (5,4) and (5, 5). The Chebotarev density theorem implies that each of the 9 possible t(p) values occurs "equally often" (that is, for a subset of the primes p = 1 (mod 6) of relative density 1/9). Using cubic reciprocity [19, Ch. 9] one calculates that 2, 3 G (Z;)3 and 6 G (Zp)3 if and only if t(p) = (2,1) or (5,5), while 2,3, 6 G (Zp)3 if and only if t(p) = (2, 5) or (5,1). Each case occurs for 2/9 of the primes that are 1 (mod 6) .
The above applications of Lemma 2.1 have all been with b =1. We note however that the conditions of Lemma 2.1 are never satisfied when S = ±{1, 2,3,4} and b =1. This is because 2 is a quadratic residue when p = 1 (mod 8), which means that both 1 and 4 are in H. The factorisations of Kp into Cay(Zp ; ±{1, 2,3,4}) in [8] were obtained by applying Lemma 2.1 with b = 2 so that G and H have index 2 and 8, respectively, in Zp. Another example where Lemma 2.1 can be applied with b =1 is when p = 919, S = ±{1, 2,3}, a = 51 and b = 3. This yields a factorisation of K9i9 into Cay(Z9i9; ±{1,2, 3}). Such a factorisation cannot be obtained by applying Lemma 2.1 with b =1 because 1, 2 and 3 are all cubes in Z;19.
The following lemma can be used to obtain factorisations of Kp, for certain values of p, in which some of the factors are isomorphic to Cay(Zp ; ±{1,2, 3}) and the others are isomorphic to Cay(Zp ; ±{1,2, 3,4}).
Lemma 2.6. Let p be prime, let H be the subgroup of Zp generated by { — 1,6}, and let d be the order of 2H in Z;/H. If there exist nonnegative integers a and ft such that d = 3a + 4ft, then there is a factorisation of Kp into a(p-1) copies of Cay(Zp ; ±{1,2,3}) and 1) copies of Cay(Zp ; ±{1,2, 3,4}).
Proof. It is sufficient to partition Z; into a(pf1) 6-tuples of the form ±{x, 2x, 3x} and ^f1) 8-tuples of the form ±{x, 2x, 3x, 4x}. Since d = 3a + 4ft, there is a partition
{{2ri-1H, 2riH, 2ri+1H} : i = 1,..., a}U
{{2ri-1H, 2riH, 2ri+1H, 2ri+2H} : i = a + 1,..., a + ft}
of {H, 2H,..., 2f-1H}. But 6 G H implies 2r^-1H = 3 • 2r*H for i =1, 2,..., a + ft. Thus, we can rewrite our partition of {H, 2H,..., 2f-1H} as
{{Hi, 2Hi, 3Hj} : i = 1,..., a} U {{Hi, 2Hj, 3Hj, 4Hj} : i = a + 1,..., a + ft},
where Hi = 2r* H for i = 1,..., a + ft.
Since -1 G H, for i = 1,..., a, Hi U 2Hi U 3Hi can be partitioned into ^ 6-tuples of the form ±{x, 2x, 3x}, and for i = a + 1,..., a + ft, Hi U 2Hi U 3Hi U 4H can be partitioned into ^ 8-tuples of the form ±{x, 2x, 3x, 4x}. If R is the set of all a^ of these 6-tuples and S is the set of all ft ^ of these 8-tuples, then RUS is a partition of the subgroup G = H U 2H U • • • U 2d-1H of Z;. Thus, if g1, g2,..., gt (t = f-!) represent the cosets of Zp/G, then
{giR : R G R,i = 1,..., t} U {giS : S G S ,i = 1,. ..,t}
162
Ars Math. Contemp. 11 (2016) 101-106
is a partition of Z* into ta^ = a(pd 1) 6-tuples of the form ±{x, 2x, 3x} and tft^ = 1) 8-tuples of the form ±{x, 2x, 3x, 4x}. This is the required partition of Zp. □
Notice that any 6-factorisation of Kp into Cay(Zp ; ±{1, 2,3}) given by Lemma 2.1 can also be obtained via Lemma 2.6. For if 1, 2, 3 represent the three distinct cosets of G/H (where G = (Zp)b and H = (Z*)3b, andp - 1 = 6a6), then it follows that {-1,6} Ç H and 2H has order 3 in G/H. This means that if H' is the subgroup of Zp generated by {-1,6}, then H' < H and 3 divides the order d of 2H' in Zp/H'. Thus, we can obtain our 6-factorisation of Kp into Cay(Zp ; ±{1,2,3}) by applying Lemma 2.6 with a = d and ft = 0. Similarly, any 8-factorisation of Kp into Cay(Zp ; ±{1, 2, 3,4}) given by Lemma 2.1 can be obtained by applying Lemma 2.6 with a = 0 and ft = 4.
However, Lemma 2.6 gives us additional factorisations such as the following. When p = 101 we have H = ±{1,6,14,17,36}, and 2H has order d =10 in Z*/H. Taking a = 2 and ft = 1, we obtain a factorisation of K101 into 10 copies of Cay(Zp ; ±{1,2,3}) and 5 copies of Cay(Zp ; ±{1, 2, 3,4}). Of course, 101 is neither 1 (mod 6) nor 1 (mod 8), so there is neither a 6-factorisation nor an 8-factorisation of K101.
2.2 Factorising complete graphs of even order
In this section we construct factorisations of K2p - I where the factors are all isomorphic to Cay(Z2p ; ±{1, 2}) or all isomorphic to Cay(Z2p ; ±{1, 2, 3,4}). We do this by considering K2p - I as a Cayley graph on a dihedral group and partitioning its connection set to generate the factors. The dihedral group D2p of order 2p has elements
r0, r1, r2,..., rp-1, s0, s1, s2,..., sp-1 and satisfies
where arithmetic of subscripts is carried out modulo p.
Lemma 2.7. Ifp > 3 is prime, then
Cay(D2p ; {r±i, sj, si+j}) = Cay(Z2p ; ±{1, 2}) for all i G Zp \ {0} and all j G Zp.
Proof. An isomorphism is given by
ro	ri	r2i	r3i .	.. r(p-i)i	Sj Si+j	s2i+j	s3i+j .	. . S(p-1)i+j
1	1	1	| .	.. |	| 1	1	| .	.. |
0	2	4	6 .	.. 2p - 2	2p - 1 1	3	5 .	.. 2p - 3
□
Lemma 2.8. Ifp > 5 is prime, then
Cay(D2p; {r±i , r±2i, sj, si+j, s2i+j, s3i+j }) = Cay(Z2p ; ±{1,2,3,4}) for all i G Zp \ {0} and all j G Zp.
B. Alspach et al.: On factorisations of complete graphs into circulant graphs and... 163
Proof. An isomorphism is given by
ro r r2i r3i ... r(p_i)i Sj si+j «2i+j s3i+j . .. s(p-i)i+j 0 2 4 6 ... 2p - 2 2p - 3 2p - 1 1 3 ... 2p - 5
□
Theorem 2.9. For each odd prime p, there is a factorisation of K2p - I into Cay(Z2p ; ±{1, 2}).
Proof. The required factorisation is F = {Xi : i e Zp \ {0}} where
Xj = Cay(D2p ; {r±2i, Sj, s_j})
for i e Zp \ {0}. Note that Xi = X-i so |F| = p—1 as required. Lemma 2.7 guarantees
that Xi = Cay(Z2p ; ±{1, 2}) for each i e Zp \ {0}. Also, r0 is the identity of D2p and each element of D2p \ {r0, s0} occurs in exactly one Xi. Thus, F is a factorisation of
Cay(D2p ; D2p \ {ro, so}) = K2p - I where the 1-factor I is Cay(D2p ; {so}).	□
Following work of Davenport [10, Theorem 5] and Weil, a special case of a result due to Moroz [23] yields the following. If p = 1 (mod 4) is prime and p > 8 x 106, then there exists an integer x such that x, x +1, x + 2, x + 3 represent all four distinct cosets of Zp/(Zp)4. A computer search using PARI/GP [25] verifies in a few minutes that such an x also exists for all p < 8 x 106 with p = 1 (mod 4), with the exceptions p =13 andp = 17. Thus, we have the following result.
Lemma 2.10. If p = 1 (mod 4) is prime with p e {13,17}, then there exists an x e Zp such that x, x +1, x + 2 and x + 3 represent all four distinct cosets of Zp/(Zp )4.
Theorem 2.11. If p = 5 (mod 8) is prime, then there is a factorisation of K2p - I into Cay(Z2p ; ±{1,2,3,4}); except that there is no factorisation of K26 - I into Cay(Z2p ; ±{1, 2, 3,4}).
Proof. We first observe that there is no factorisation of K26 - I into graph Cay(Z2p; ±{1,2,3,4}). If such a factorisation exists, then we can assume without loss of generality that the vertex set is Z26 and that Cay(Z26 ; ±{1,2,3,4}) is a factor. But no edge of Cay(Z26 ; ±{7}) (for example) occurs in a complete subgraph of order 5 in Cay(Z26 ; ±{5,6,7, 8, 9,10,11,12,13}). Since Cay(Z26 ; ±{1, 2,3,4}) contains a complete subgraph of order 5, it follows that there is no factorisation of K26 - I into graph Cay(Z2p ; ±{1, 2, 3, 4}).
Let p = 5 (mod 8) be prime with p = 13. By Lemma 2.10, there exists an x e Zp such that x, x + 1, x + 2 and x + 3 represent all four distinct cosets of Zp/(Zp)4. By Lemma 2.8,
Cay(D2p ; {r±i, r±2, sx, sx+i, s^+2, sx+3}) = Cay(Z2p ; ±{1, 2, 3, 4}).
Now let H = (Zp)4 act on the subscripts of the connection set {r±1, r±2, sx, sx+1, sx+2, sx+3} and consider the collection S1, S2,..., Sp-1 of subsets of D2p thus formed.
164
Ars Math. Contemp. 11 (2016) 101-106
We show that {Cay(D2p ; Sj) : i = 1,2,..., } is a factorisation of K2p - I into
Cay(Z2p ; ±{1,2,3,4}). If h G H, then
Cay(D2p; {r±h r±2h Sh(x+l), sh(x+2), sh(x+3)}) = Cay(Z2p; ±{1,2,3,4})
by Lemma 2.8 (indeed this is true for any h G Zp) so it remains only to verify that we have a decomposition of K2p - I. To do this we observe that S1, S2,..., Sp-i partitions
D2p \ {r0, so} (r0 is the identity in D2p and Cay(D2p ; {so}) is a 1-factor in K2p). We have Hx U H(x + 1) U H(x + 2) U H(x + 3) = Zp \ {0}. Also, since p = 5 (mod 8) we have -1 G (Zp2, -1 G (Z;)4 and 2 G (Z;)2 (by the law of quadratic reciprocity). Thus, {±h : h G H} U {±2h : h G H} = Zp \ {0}. So Si, S2,..., Sp-i does indeed partition D2p \ {r0, s0} and we have the required decomposition.	□
3 2-factorisations of circulant graphs
In this section we present various results on 2-factorisations of circulant graphs, beginning with a couple of known results. Lemma 3.1 was proved independently in [4] and [27], and is a special case of a result in [6]. Lemma 3.2 was proved in [8].
Lemma 3.1. ([4, 27]) If n > 5 and F is any 2-regular graph of order n, then there is a 2-factorisation of Cay(Zn ; ±{1, 2}) into a copy of F and a Hamilton cycle.
Lemma 3.2. ([8]) If n > 9 and F is a 2-regular graph of order n, then there is a 2-factorisation of Cay(Zn ; ±{1,2,3,4}) into F with the definite exceptions of F = C4 U C5 and F = C3 U C3 U C3 U C3 U C3, and the following possible exceptions.
(1)	F = C3 U C3 U • • • U C3 when n = 3, 6 (mod 9), n > 21.
(2)	F = C4 U C4 U • • • U C4 when n = 4 (mod 8), n > 20.
(3)	F = C3 U C3 U • • • U C3 U C4 when n = 1 (mod 3), n > 19.
(4)	F = C3 U C4 U C4 U • • • U C4 when n = 7 (mod 8), n > 23.
We now obtain results on 2-factorisations of Cay(Zn ; ±{1,2, 3}), but first we need some definitions and notation. For each m > 1, the graph with vertex set {0,1,..., m + 2} and edge set {{i, i + 1}, {i + 1, i + 3}, {i, i + 3} : i = 0,1,..., m - 1} is denoted by jm2'3. If F is a 2-regular graph of order m, and there exists a decomposition {H1, H2, H3} of J,^2'3 into F such that
(1)	V(H1) = {0, 1,. .., m + 2} \ {m, m + 1, m + 2},
(2)	V(H2) = {0,1,..., m + 2} \ {0, 2, m + 1}, and
(3)	V(H3) = {0,1,..., m + 2} \ {0,1, m + 2},
then we shall write J,^2'3 ^ F. Notice that for i = 1,2,3, the subgraph Hj of J,^2'3 contains exactly one vertex from each of {0, m}, {1, m + 1} and {2, m + 2}.
Lemma 3.3. If n > 7 and F is a 2-regular graph of order n such that there exists a decomposition J^'2'3 ^ F, then there exists a 2-factorisation of Cay(Zn ; ±{1, 2,3}) into F.
B. Alspach et al.: On factorisations of complete graphs into circulant graphs and... 165
Proof. For each i G {0,1, 2}, identify vertex i of J'2'3 with vertex n + i. The resulting graph is Cay(Zn ; ±{1, 2, 3}) and the 2-regular graphs in the decomposition J^'2'3 ^ F become the required 2-factors.	□
Lemma 3.4. If F and F' are vertex-disjoint 2-regular graphs and there exist decompositions J|t/2(f)| ^ F and J"|V'2('f')| ^ F', then there exists a decomposition J"|t>2('j3)| + |V(F/) ^
F II F '.
Proof. Let r and s be the respective orders of F and F', let {H^ H2, H3} be a decomposition J,1'2'3 ^ F and let {Hi, H2, H3} be a decomposition J1'2'3 ^ F'. Apply the translation x ^ x + r to the decomposition {Hi, H2, H3} to obtain a decomposition {Hi', H2', H3'} of a copy of J1'2'3 having vertex set r, r + 1,...,r + s + 2 (H/' being the translation of H/ for i G {1, 2, 3}). It is clear that D = {Hi U Hi', H U H2', H3 U H3'} is a decomposition J1|2i'3 ^ F U F'. Properties (1)-(3) in the definition of J,1'2'3 ^ F ensure that H and H/' are vertex-disjoint for i G {1, 2,3}, and that
(1)	V(H1 U Hi') = {0,1,. .., r + s + 2} \ {r + s, r + s + 1, r + s + 2},
(2)	V(H2 U H2') = {0,1,..., r + s + 2} \ {0, 2, r + s + 1}, and
(3)	V(H3 U H3') = {0,1,..., r + s + 2}\{0,1,r + s + 2}.
□
Lemma 3.5. For each m > 4, J^2'3 ^ Cm.
Proof. For m G {4,5,6}, H1, H2, H3 are as defined in the following table.
m	Hi	H2	H3
4	(0,1, 2, 3)	(1, 3, 6,4)	(2,4, 3, 5)
5	(0,1, 2,4, 3)	(1, 3, 5, 7,4)	(2, 3, 6,4, 5)
6	(0,1, 2, 5,4, 3)	(1, 3, 5, 8, 6,4)	(2,4, 7, 5, 6, 3)
For m > 7 and odd
•	Hi contains the edges {0,1}, {1,2}, {0, 3}, {m - 2, m - 1} and {i, i + 2} for i G {2, 3, .. ., m - 3},
•	H2 contains the edges {1, 3}, {m — 2, m}, {m, m + 2}, {m — 1, m + 2}, {i, i + 1} for i G {4,6,..., m - 3} and {i, i + 3} for i G {1,3,..., m - 4}, and
•	H3 contains the edges {2, 3}, {m - 2, m +1}, {m -1, m}, {m -1, m +1}, {i, i + 1} for i G {3, 5,..., m - 4} and {i, i + 3} for i G {2,4,..., m - 3}.
For m > 8 and even
•	H1 contains the edges {0,1}, {1,2}, {3,4}, {0, 3}, {2,5}, {m - 2,m - 1} and {i,i + 2} for i G {4, 5,..., m - 3},
•	H2 contains the edges {1, 3}, {1,4}, {3, 5}, {m-2, m}, {m, m+2}, {m-1, m+2}, {i, i + 1} for i G {5, 7,..., m - 3} and {i, i + 3} for i G {4,6,..., m - 4}, and
•	H3 contains the edges {2,4}, {m - 2, m +1}, {m -1, m}, {m - 1,m +1}, {i,i + 1} for i G {2,4,..., m - 4} and {i, i + 3} for i G {3, 5,..., m - 3}.
□
166	Ars Math. Contemp. 11 (2016) 101-106
Lemma 3.6. For m = 8 and for each m > 10, J^2'3 ^ C3 U Cm-3. Proof. For m G {8,10,11}, Hi, H2, H3 are as defined in the following table.
m	
8	hi = (4, 6, 7) u (0,1, 2, 5, 3) h2 = (7, 8,10) u (1, 3, 6, 5,4) h3 = (2, 3,4) u (5, 7, 9, 6, 8)
10	hi = (7, 8, 9) u (0,1, 2,4, 5, 6, 3) h2 = (1, 3,4) u (5, 7, 6, 9,12,10, 8) h3 = (2, 3, 5) u (4, 6, 8,11, 9,10, 7)
11	hi = (8, 9,10) u (0,1, 2,4, 5, 7, 6, 3) h2 = (1, 3,4) u (5, 6, 9,11,13,10, 7, 8) h3 = (2, 3, 5) u (4, 6, 8,11,10,12, 9, 7)
For m > 12 and even
•	Hi consists of the 3-cycle (m - 3, m - 2, m - 1) and the (m - 3)-cycle with edges
{0,1}, {0, 3}, {1, 2}, {2, 4}, {m - 5, m - 4}, {i, i + 1} for i G {4, 6,..., m - 6} and {i, i + 3} for i G {3,5,..., m - 7},
•	H2 consists of the 3-cycle (1, 3,4) and the (m - 3)-cycle with edges {5,7}, {m -
5, m - 2}, {m - 4, m - 3}, {m - 2, m}, {m, m + 2}, {m - 1, m + 2}, {i, i + 1} for i G {5, 7,..., m - 7} and {i, i + 3} for i G {6,8,..., m - 4}, and
•	H3 consists of the 3-cycle (2,3,5) and the (m - 3)-cycle with edges {4,6}, {4,7},
{m - 2, m + 1}, {m - 3, m}, {m - 1, m}, {m - 1, m +1} and {i, i + 2} for i G {6, 7,..., m - 4}.
For m > 13 and odd
•	Hi consists of the 3-cycle (m - 3, m - 2, m - 1) and the (m - 3)-cycle with edges
{0,1}, {0, 3}, {1, 2}, {2, 4}, {3, 6}, {4, 5}, {5, 7}, {m - 5, m - 4}, {i, i + 1} for i G {7, 9,..., m - 6} and {i, i + 3} for i G {6, 8,..., m - 7},
•	H2 consists of the 3-cycle (1, 3,4) and the (m - 3)-cycle with edges {5,6}, {m -
5, m - 2}, {m - 4, m - 3}, {m - 2, m}, {m, m + 2}, {m - 1, m + 2}, {i, i + 1} for i G {6, 8,..., m - 7} and {i, i + 3} for i G {5,7,..., m - 4}, and
•	H3 consists of the 3-cycle (2,3,5) and the (m - 3)-cycle with edges {4,6}, {4,7},
{m - 2, m + 1}, {m - 3, m}, {m - 1, m}, {m - 1, m +1} and {i, i + 2} for i G {6, 7,..., m - 4}.
□
Lemma 3.7. Let n > 7 and let F be a 2-regular graph of order n. If v3(F) < v5 (F) + Vj(F) where vm(F) denotes the number of m-cycles in F, then there exists a 2-factorisation of Cay(Zn; ±{1,2, 3}) into F.
Proof. If n > 7 and F is a 2-regular graph of order n such that v3(F) < v5(F) + vi(F), then F can be written as a vertex-disjoint union of 2-regular graphs Gi, G2, ..., Gt where each Gj is isomorphic to either
•	Cm with m > 4, or
B. Alspach et al.: On factorisations of complete graphs into circulant graphs and... 
167
• C3 U Cm-3 with m = 8 or m > 10.
12 3
By Lemmas 3.5 and 3.6 we have a decomposition J|V(g )| ^ G for i = 1,2,... ,t. Applying Lemma 3.4 we obtain a decomposition J,1'2'3 ^ F, and from this we obtain the required 2-factorisation of Cay(Zn; ±{1, 2, 3}) into F by applying Lemma 3.3.	□
We can obtain an analogue of Lemma 3.7 for Cay(Zn ; ±{1, 3,4}) by using similar methods, but we will require F to have girth at least 6. The graph with vertex set
{0,1,..., m + 3} and edge set {{i, i + 1}, {i + 1, i + 4}, {i, i + 4} : i = 0,1,... ,m -1} is denoted by J,13'4. We write Jm3'4 ^ F when there exists a decomposition {H1, H2, H3} of J,^3'4 into a 2-regular graph F such that
(1)	V(H1) = {0, 1,.. ., m + 3} \ {m, m + 1, m + 2, m + 3},
(2)	V(H2) = {0,1,..., m + 3} \ {0, 3, m + 1, m + 2}, and
(3)	V(H3) = {0,1,..., m + 3} \ {0,1, 2, m + 3}.
Notice that for i = 1, 2, 3, the subgraph Hj of J^3'4 contains exactly one vertex from each of {0, m}, {1, m + 1}, {2, m + 2} and {3, m + 3}. It is clear that the proofs of Lemmas 3.3 and 3.4 can be easily modified to give the following two results.
Lemma 3.8. If n > 9 and F is a 2-regular graph of order n such that there exists a decomposition J^'3'4 ^ F, then there exists a 2-factorisation of Cay(Zn ; ±{1, 3,4}) into F.
Lemma 3.9. If F and F' are vertex-disjoint 2-regular graphs and there exist decompositions J|T>3('i4)| ^ F and J|V3(f')| ^ F', then there exists a decomposition J"|T>3'i4)| + |V(F/)| ^
FuF '.
Lemmas 3.8 and 3.9 allow us to obtain 2-factorisations of Cay(Zn ; ±{1, 3,4}) via the same method we used in the case of Cay(Zn ; ±{1, 2, 3}), providing we can find appropriate decompositions of J^3'4. We now do this.
Lemma 3.10. For m = 6, m = 7 and each m > 9, J,^3'4 ^ Cm.
Proof. For m G {6,7,9,10}, H1, H2, H3 are as defined in the following table.
m	Hi	H2	H3
6	(0,1, 5, 2, 3,4)	(1, 2, 6, 9, 5,4)	(3, 6, 5, 8,4, 7)
7	(0,1, 2, 3, 6, 5,4)	(1,4, 7,10, 6, 2, 5)	(3,4, 8, 5, 9, 6, 7)
9	(0,1, 2, 3, 7, 6, 5, 8,4)	(1,4, 7, 8,12, 9, 6, 2, 5)	(3,4, 5, 9, 8,11, 7,10, 6)
10	(0,1, 2, 3, 6, 9, 5, 8, 7,4)	(1,4, 8, 9,13,10, 7, 6, 2, 5)	(3,4, 5, 6,10, 9,12, 8,11, 7)
For m > 11 and odd
•	H1 contains the edges {0,1}, {0,4}, {1, 2}, {2,3}, {3,7}, {5,6}, {m - 3, m - 2}, {m — 5, m — 1}, {m — 4, m — 1} and {i, i + 4} for i G {4, 5,..., m — 6},
•	H2 contains the edges {1,4}, {1,5}, {2,5}, {2,6}, {4,7}, {m, m + 3}, {m — 1, m + 3}, {m — 2, m — 1}, {m — 3, m}, {i, i + 1} for i G {7, 9,..., m — 4} and {i, i + 3} for i G {6,8,..., m — 5}, and
168
Ars Math. Contemp. 11 (2016) 101-106
•	H3 contains the edges {3, 4}, {3, 6}, {4, 5}, {m-1, m}, {m—2, m+1}, {m-1, m+ 2}, {m — 4, m}, {m — 3, m + 1}, {m — 2, m + 2}, {i, i + 1} for i G {6, 8,..., m — 5} and {i, i + 3} for i G {5,7,..., m — 6}.
For m > 12 and even
•	Hi contains the edges {0,1}, {0,4}, {1,2}, {2,3}, {3, 6}, {4, 7}, {5, 6}, {5,9}, {m — 5, m — 2}, {m — 4, m — 3}, {m — 4, m — 1}, {m — 2, m — 1}, {i, i + 1} for i G {7, 9,..., m — 7} and {i, i + 3} for i G {8,10,..., m — 6},
•	H2 contains the edges {1,4}, {1,5}, {2,5}, {2, 6}, {4, 8}, {m — 6,m — 2}, {m — 5, m — 4}, {m — 5, m — 1}, {m — 3, m — 2}, {m — 3, m}, {m — 1, m+3}, {m, m+3}, {i, i + 1} for i G {6,8,..., m — 8} and {i, i + 3} for i G {7, 9,..., m — 7}, and
•	H3 contains the edges {3,4}, {3,7}, {4,5}, {5, 8}, {6, 9}, {m — 6, m — 5}, {m — 4, m}, {m — 3, m +1}, {m — 2, m + 1}, {m — 2, m + 2}, {m — 1, m}, {m — 1, m + 2} and {i, i + 4} for i G {6,7,..., m — 7}.
□
Lemma 3.11. For each m > 14, J,^3'4 ^ C8 U Cm-8.
Proof. For m G {14,15,16,17}, H1, H2, H3 are as defined in the following table.
m	
14	hi = (0,1, 2, 3, 7, 8, 5,4) u (6, 9,13,12,11,10) h2 = (8,11,14,17,13,10, 9,12) u (1,4, 7, 6, 2, 5) h3 = (7,10,14,13,16,12,15,11) u (3,4, 8, 9, 5, 6)
15	hi = (0,1, 2, 3, 6, 5, 8,4) u (7,10,14,13, 9,12,11) h2 = (1,4, 7, 8, 9, 6, 2, 5) u (10,11,14,18,15,12,13) h3 = (8,11,15,14,17,13,16,12) u (3,4, 5, 9,10, 6, 7)
16	hi = (0,1, 5, 6, 2, 3, 7,4) u (8, 9,10,11,15,14,13,12) h2 = (1, 2, 5, 9, 6, 7, 8,4) u (10,13,16,19,15,12,11,14) h3 = (3,4, 5, 8,11, 7,10, 6) u (9,12,16,15,18,14,17,13)
17	hi = (0,1, 2, 3, 7, 6, 5,4) u (8, 9,13,16,12,15,14,10,11) h2 = (1,4, 8,12, 9, 6, 2, 5) u (7,10,13,14,17, 20,16,15,11) h3 = (3,4, 7, 8, 5, 9,10, 6) u (11,12,13,17,16,19,15,18,14)
For m > 18 and even
•	H1 consists of the 8-cycle (0,1, 5,6,2, 3, 7,4) and the (m — 8)-cycle with edges {8, 9}, {9,10}, {10, 11}, {8,12}, {m — 5, m — 1}, {m — 4, m — 3}, {m — 3, m — 2}, {m — 2, m — 1} {i, i + 1} for i G {12,14,..., m — 6} and {i, i + 3} for i G {11,13,...,m — 7},
•	H2 consists of the 8-cycle (1, 2, 5,9,6, 7, 8,4) and the (m — 8)-cycle with edges {10,13}, {11, 12}, {m — 6, m — 2}, {m — 5, m — 2}, {m — 4, m — 1}, {m — 3, m}, {m — 1, m + 3}, {m, m + 3} and {i, i + 4} for i G {10,11,..., m — 7}, and
•	H3 consists of the 8-cycle (3,4, 5,8,11,7,10,6) and the (m — 8)-cycle with edges {9, 12}, {9,13}, {m — 4, m}, {m — 3, m + 1}, {m — 2, m + 1}, {m — 2, m + 2}, {m — 1, m}, {m — 1, m + 2}, {i, i +1} for i G {13,15,..., m — 5} and {i, i + 3} for i G {12,14, ...,m — 6}.
B. Alspach et al.: On factorisations of complete graphs into circulant graphs and... 169
For m > 19 and odd
•	H1 consists of the 8-cycle (0,1, 2,3,7,6, 5,4) and the (m - 8)-cycle with edges {8, 9}, {8,11}, {9,13}, {10,11}, {10,14}, {12,15}, {12,16}, {m - 4, m - 1}, {m - 3, m - 2} and {i, i + 4} for i G {13,14,..., m - 5},
•	H2 consists of the 8-cycle (1,4, 8,12, 9,6,2, 5) and the (m - 8)-cycle with edges {7, 10}, {7,11}, {10,13}, {11, 15}, {m - 4, m - 3}, {m - 3, m}, {m - 2, m - 1}, {m - 1, m + 3}, {m, m + 3}, {i, i +1} for i G {13,15,..., m - 6} and {i, i + 3} for i G {14,16,..., m - 5}, and
•	H3 consists of the 8-cycle (3,4, 7,8,5,9,10, 6) and the (m - 8)-cycle with edges {11,12}, {11, 14}, {12,13}, {m - 4, m}, {m - 3, m + 1}, {m - 2, m + 1}, {m -2, m + 2}, {m - 1, m}, {m - 1, m + 2}, {i, i + 1} for i G {14,16,..., m - 5} and {i, i + 3} for i G {13,15,..., m - 6}.
□
Lemma 3.12. Jf'4 ^ C8 U C8 U C8. Proof. Take
hi = (0,1, 2, 3, 6, 5, 8,4) u (7,10, 9,12,13,14,15,11) u (16,17,18,19, 23, 22, 21, 20), h2 = (1,4, 7, 8, 9, 6, 2, 5) u (10,11,12,15,16,13,17,14) u (18, 21, 24, 27, 23, 20,19, 22), and h3 = (3,4, 5, 9,13,10, 6, 7) u (8,11,14,18,15,19,16,12) u (17, 20, 24, 23, 26, 22, 25, 21).
□
The following result is an analogue of Lemma 3.7 for 2-factorisations of Cay(Zn; ±{1, 3,4}).
Lemma 3.13. If n > 9 and F is a 2-regular graph of order n with girth at least 6, then there exists a 2-factorisation of Cay(Zn ; ±{1, 3,4}) into F.
Proof. If n > 9 and F is a 2-regular graph of order n with girth at least 6, then F can be written as a vertex-disjoint union of 2-regular graphs Gi, G2,..., Gt where each Gj is isomorphic to either
•	Cm with m = 6, 7 or m > 9,
•	C8 U Cm-8 with m > 14, or
•	Cg u Cg u c8.
1 3 4
By Lemmas 3.10,3.11 and 3.12 we have a decomposition j|V(g )| ^ Gj for i = 1, 2,..., t. Applying Lemma 3.9 we obtain a decomposition J>3 >4 ^ F, and from this we obtain the required 2-factorisation of Cay(Zn; ±{1, 3,4}) into F by applying Lemma 3.8.	□
4 2-factorisations and the Oberwolfach Problem
In this section we use results from the preceding sections to obtain results on the Oberwolfach Problem (and an additional result on 2-factorisations of Kn - I into a number of specified 2-factors and Hamilton cycles). We will also use the following corollary of Lemma 3.2 which was proved in [8].
170
Ars Math. Contemp. 11 (2016) 101-106
Lemma 4.1. ([8]) If there exists a factorisation of Kn or of Kn —I into Cay(Zn ; ±{1,2, 3, 4}), then OP(F ) has a solution for each 2-regular graph F of order n, with the exception that there is no solution to OP(C4 U C5).
Theorem 4.2. If p = 5 (mod 8) is prime, then OP(F) has a solution for every 2-regular graph F of order 2p.
Proof. The case p = 13 is covered in [13]. For p = 13, Theorem 2.11 gives us a factorisation of K2p — I into Cay(Z2p ; ±{1, 2, 3,4}) and the result then follows by Lemma 4.1.	□
Theorem 4.3. Let P be the set of primes given by p G P if and only if p > 7 and neither 4 nor 32 is in the subgroup of Zp generated by { — 1, 6}. Then P is infinite and if p G P, then OP(F) has a solution for every 2-regular graph F of order p satisfying v3(F) < v5(F) + Y^n=7 vi(F) where vm(F) denotes the number of m-cycles in F.
Proof. Let p be prime such that p = 1 (mod 6), 2,3 G (Zp)3 and 6 G (Zp)3. Theorem 2.5 says that there are infinitely many such p. We shall show that p G P, which shows that P is also infinite. We have —1 G (Zp)3, and this together with the fact that 6 g (Zp)3 implies that the subgroup of Zp generated by {—1,6} is a subgroup of (Zp)3. Since it follows from 2 G (Zp)3 that 4, 32 G (Zp)3, neither 4 nor 32 is in the subgroup of Zp generated by { —1,6}. That is, p G P.
Now let p be an arbitrary element of P and let G be the subgroup of Zp generated by { — 1,6}. The condition that neither 4 nor 32 is in G implies that the order d of 2G in Zp/G is neither 1, 2 nor 5, and so there exist non-negative integers a and 0 such that d = 3a + 40. Thus, by Lemma 2.6 there is a factorisation of Kp in which each factor is either Cay(Zp ; ±{1, 2, 3}) or Cay(Zp ; ±{1,2, 3,4}).
Let F be a 2-regular graph of order p satisfying v3 (F) < v5 (F) + J2n=7 V (F). Lemma 3.7 gives us a 2-factorisation of Cay(Zp ; ±{1,2, 3}) into F, and Lemma 3.2 gives us a 2-factorisation of Cay(Zp ; ±{1,2,3,4}) (the facts that p is prime and that v3(F) < v5 (F) + J2n=7 vi(F) imply that F is not amongst the possible exceptions listed in Lemma 3.2). The result follows.	□
Theorem 4.4. Let P be the set of primes such that p G P if and only if p = 1 (mod 6) and 2, 3, 6 G (Zp)3. Then P is infinite and if p G P, then OP(F ) has a solution for every 2-regular graph F of order p with girth at least 6.
Proof. By Theorem 2.5, P is infinite. If p G P, then Theorem 2.4 gives us a factorisation of Kp into Cay(Zp ; ±{1,3,4}), and the result then follows by applying Lemma 3.13 to each factor (7 G P so Lemma 3.13 can indeed be applied).	□
For each odd prime p, the following theorem states there is a 2-factorisation of K2p — I into p-1 prescribed 2-factors and p-1 Hamilton cycles.
Theorem 4.5. If p is an odd prime and Gi, G2,..., G p-i are 2-regular graphs of order
2
2p, then there is a 2-factorisation {Fi, F2,..., Fp-i} of K2p — I such that Fi = Gi for i = 1, 2,..., p-1 and Fi is a Hamilton cycle for i = £++i, ,... ,p — 1.
Proof. By Theorem 2.9 there is a factorisation of K2p — I into Cay(Zp ; ±{1, 2}). By Lemma 3.1, each copy of Cay(Zp ; ±{1,2}) can be factored into any specified 2-regular graph of order 2p and a Hamilton cycle. The result follows.	□
B. Alspach et al.: On factorisations of complete graphs into circulant graphs and... 171
5 Isomorphic 2-factorisations of complete multigraphs
The complete multigraph of order n and multiplicity s is denoted by sKn. It has s distinct edges joining each pair of distinct vertices.
Lemma 5.1. If p is an odd prime and S = ±{d1,d2,... ,ds} Ç Zp, then there exists a 2s-factorisation of sKp into Cay(Zp ; S).
Proof. The required factorisation is given by {Cay(Zp ; w®S) : i = 0,1,..., } where w is primitive in Zp and w®S = {w®s : s G S}.	□
Theorem 5.2. If p is an odd prime and F is any 2-regular graph of order p satisfying v3(F) < v5(F) + Vj(F), where vm(F) denotes the number of m-cycles in F, then there exists a 2-factorisation of 3Kp into F.
Proof. The cases p = 3 and p = 5 are trivial so assume p > 7. By Lemma 5.1 there exists a 6-factorisation of 3Kp into Cay(Zp ; ±{1,2,3}), and by Lemma 3.7 each such 6-factor has a 2-factorisation into F.	□
Theorem 5.3. If p is an odd prime and F is any 2-regular graph of order p, then there exists a 2-factorisation of 4Kp into F.
Proof. The cases p = 3 andp = 5 are trivial. Since solutions to OP(C7) and OP(C3 UC4) exist, the case p = 7 can be dealt with by taking four copies of these 2-factorisations of K7. So we may assume p > 11. By Lemma 5.1 there exists an 8-factorisation of 4Kp into Cay(Zp ; ±{1,2, 3,4}), and by Lemma 3.2 each such 8-factor has a 2-factorisation into F; except in the case where F is one of the listed exceptions or possible exceptions in Lemma 3.2. These are easily dealt with as follows. Since p is prime the only relevant exceptions are F = C3 U C3 U • • • U C3 U C4 where the number of copies of C3 is at least 5, and F = C3 U C4 U C4 U • • • U C4 where the number of copies of C4 is odd and at least 5. However, it is known that for each such F, there is a 2-factorisation of Kp into F; the former case is covered in [11], and the latter case is covered in [21]. Thus, by taking four copies of these 2-factorisations of Kp, we obtain the required 2-factorisations of 4Kp. □
Theorem 5.4. Let p be an odd prime and let F be a 2-regular graph of order p. If A = 0 (mod 4), then there exists a 2-factorisation of AKp into F. Moreover, if F satisfies v3(F ) < v5(F ) + Vj(F), where vm(F) denotes the number of m-cycles in F, then the result also holds for A = 3 and for all A > 6.
Proof. For the given values of A, it is trivial to factorise AKp such that each factor is either 3Kp or 4Kp, and with each factor being 4Kp when A = 0 (mod 4). Thus, the result follows by Theorems 5.2 and 5.3.	□
Acknowledgement. The authors gratefully acknowledge the support of the Australian Research Council via grants DE120100040, DP0770400, DP120100790, DP120103067, DP150100506, DP150100530 and DP130102987.
172
Ars Math. Contemp. 11 (2016) 101-106
References
[1]	B. Alspach and R. Haggkvist, Some observations on the Oberwolfach problem, J. Graph Theory 9 (1985), 177-187.
[2]	B. Alspach, J. Morris and V. Vilfred, Self-complementary circulant graphs, Ars Combin. 53 (1999), 187-191.
[3]	B. Alspach, P. J. Schellenberg, D. R. Stinson and D. Wagner, The Oberwolfach problem and factors of uniform odd length cycles, J. Combin. Theory Ser. A 52 (1989), 20-43.
[4]	D. Bryant, Hamilton cycle rich two-factorisations of complete graphs, J. Combin. Des. 12 (2004), 147-155.
[5]	D. Bryant and P. Danziger, On bipartite 2-factorisations of Kn — I and the Oberwolfach problem, J. Graph Theory 68 (2011), 22-37.
[6]	D. Bryant and G. Martin, Some results on decompositions of low degree circulant graphs, Australas. J. Combin. 45 (2009), 251-261.
[7]	D. Bryant and C. A. Rodger, Cycle decompositions, in: C. J. Colbourn, J. H. Dinitz (eds.), The CRC Handbook of Combinatorial Designs, 2nd edition CRC Press, Boca Raton, 2007, 373-382.
[8]	D. Bryant and V. Scharaschkin, Complete solutions to the Oberwolfach problem for an infinite set of orders, J. Combin. Theory Ser. B 99 (2009), 904-918.
[9]	M. Buratti, A packing problem and its application to Bose's families, J. Combin. Des. 4 (1996), 457-472.
[10]	H. Davenport, On character sums in finite fields, Acta Math. 71 (1939), 99-121.
[11]	I. J. Dejter, F. Franek, E. Mendelsohn, and A. Rosa, Triangles in 2-factorizations, J. Graph Theory 26 (1997), 83-94.
[12]	I. J. Dejter, C. Lindner and A. Rosa, The number of 4-cycles in 2-factorizations of Kn, J. Combin. Math. Combin. Comput. 28 (1998), 101-112.
[13]	A. Deza, F. Franek, W. Hua, M. Meszka and A. Rosa, Solutions to the Oberwolfach problem for orders 18 to 40, J. Combin. Math. Combin. Comput. 74 (2010), 95-102.
[14]	E. Dobson and M. Sajna, Almost self-complementary circulant graphs, Discrete Math. 278 (2004), 23-44.
[15]	D. Froncek, A. Rosa and J. Siran, The existence of self-complementary circulant graphs, European J. Combin. 17 (1996), 625-628.
[16]	R. K. Guy, Unsolved combinatorial problems, Proceedings of the Conference on Combinatorial Mathematics and Its Applications, Oxford, 1967 (ed. D. J. A. Welsh, Academic Press, New York, 1971) p. 121.
[17]	R. Haggkvist, A lemma on cycle decompositions, Ann. Discrete Math. 27 (1985), 227-232.
[18]	D. G. Hoffman and P. J. Schellenberg, The existence of Ck -factorizations of K2n — F, Discrete Math. 97 (1991), 243-250.
[19]	K. Ireland and M. Rosen, A Classical Introduction to Modern Number Theory, 2nd ed., Graduate Texts in Mathematics 84, Springer-Verlag, 1990.
[20]	G. J. Janusz Algebraic Number Fields, 2nd ed., Graduate Studies in Mathematics Vol 7, American Mathematical Society, 1996.
[21]	E. Kohler, Das Oberwolfacher problem, Mitt. Math. Ges. Hamburg 10 (1973), 52-57.
[22]	K. Momihara, On cyclic 2(k — 1)-support (n, k)k-1 difference families, Finite Fields Appl. 15 (2009), 415-427.
B. Alspach et al.: On factorisations of complete graphs into circulant graphs and... 173
[23]	B. Z. Moroz, The distribution of power residues and non-residues, Vestnik Leningrad. Univ. 16 (1961), 164-169.
[24]	A. Munemasa, On perfect t-shift codes in abelian groups, Des. Codes Cryptogr. 5 (1995), 253259.
[25]	PARI/GP, version 2.5.1, Bordeaux, 2013, http://pari.math.u-bordeaux.fr/.
[26]	C. Praeger, C. H. Li and L. Stringer, Common circulant homogeneous factorisations of the complete digraph, Discrete Math. 309 (2009), 3006-3012.
[27]	C. A. Rodger, Hamilton decomposable graphs with specified leaves, Graphs Combin. 20 (2004), 541-543.
[28]	S. Szabô, Topics in factorization of abelian groups, Birkhuser Verlag, Basel, 2004.
[29]	T. Traetta, A complete solution to the two-table Oberwolfach problems, J. Combin. Theory Ser. A 120 (2013), 984-997.
[30]	J. Turner, Point-symmetric graphs with a prime number of points, J. Combin. Theory 3 (1967), 136-145.