¿^creative	, ars mathematica
^commons	contemporánea
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 12 (2017) 219-233
Cyclic and symmetric hamiltonian cycle systems of the complete multipartite graph: even number of parts
Francesca Merola
Dipartimento di Matematica e Fisica, Universita Roma Tre, Largo S.L. Murialdo 1,1-00146 Roma, Italy
Anita Pasotti
DICATAM - Sez. Matematica, Universita degli Studi di Brescia, Via Branze 43, I-25123 Brescia, Italy
Marco Antonio Pellegrini
Dipartimento di Matematica e Fisica, Universita Cattolica del Sacro Cuore, Via Musei 41, I-25121 Brescia, Italy
Received 12 May 2015, accepted 28 October 2015, published online 5 December 2016 Abstract
In this paper, we present a complete solution to the existence problem for a cyclic hamiltonian cycle system for the complete multipartite graph with an even number of parts all of the same cardinality. We also give necessary and sufficient conditions for the system to be symmetric as well.
Keywords: Hamiltonian cycle, cyclic cycle system, symmetric hamiltonian cycle system, complete multipartite graph. Math. Subj. Class.: 05B30
1 Introduction
Throughout this paper, Kv will denote the complete graph on v vertices and, if v is even, Kv — I will denote the cocktail party graph of order v, namely the graph obtained from Kv by removing a 1-factor I, that is, a set of | pairwise disjoint edges. Also Kmxn will denote the complete multipartite graph with m parts of same cardinality n; if n = 1, we
E-mail addresses: merola@mat.uniroma3.it (Francesca Merola), anita.pasotti@unibs.it (Anita Pasotti), marcoantonio.pellegrini@unicatt.it (Marco Antonio Pellegrini)
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
220
Ars Math. Contemp. 12 (2017) 383-413
may identify Kmx 1 with Km, while if n = 2, Kmx2 is nothing but the cocktail party graph
K2m - I.
For any graph r we write V(T) for the set of its vertices and E(T) for the set of its edges. We denote by C = (c0, c1,..., c£-1) the cycle of length i whose edges are [c0, c1], [c1, c2],..., [ce_1, c0]. An i-cycle system of a graph r is a set B of cycles of length i whose edges partition E(r); clearly a graph may admit a cycle system only if the degree of each vertex is even. For general background on cycle systems we refer to the surveys [7, 8]. An i-cycle system B of r is said to be hamiltonian if i = |V(r)|, and it is said to be cyclic if we may identify V(r) with the cyclic group Zv, and if for any C = (c0, c1,..., c£_1) e B, we have also C + 1 = (c0 + 1, c1 + 1,..., c£_1 + 1) e B. The existence problem for cyclic cycle systems of Kv has generated a considerable amount of interest. Many authors have contributed to give a complete answer in the case v = 1 or i (mod 2i) (see [10, 11, 19, 20, 21, 22, 26]). We point out in particular that the existence problem of a cyclic hamiltonian cycle system (HCS, for short) for Kv has been solved by Buratti and Del Fra in [11], and that for Kv - I it has been solved by Jordon and Morris [17].
The existence problem for cycle systems of the complete multipartite graph has not been solved yet, but we have many interesting recent results on this topic (see for instance [4, 5, 24, 25]). Still, very little is known about the same problem with the additional constraint that the system be cyclic. We have a complete solution in the following very special cases: the length of the cycles is equal to the cardinality of the parts [12]; the cycles are hamiltonian and the parts have cardinality two [14, 17]. We have also some partial results in [3].
Hamiltonian cycle systems of Kmxn have been shown to exist ([18]) whenever the degree of each vertex of the graph, that is (m - 1)n, is even; in this paper we start investigating the existence of cyclic hamiltonian cycle systems of Kmxn, and completely solve the problem when m is even.
We also consider the existence of a symmetric HCS for Kmxn with n > 1, a concept recently introduced by Schroeder in [23] generalizing the notion of symmetry given in [6] for cocktail party graphs: in this definition, an HCS for Kmxn is n-symmetric if each cycle in the system is invariant under a fixed-point-free automorphism of order n. We will show that the cycle systems we shall construct in will turn out to be symmetric in this sense.
The paper is organized as follows: after some preliminary notes in Section 2 on the methods we shall use, in Section 3 we establish a necessary condition in the case n even for the existence of a cyclic cycle system (not necessarily hamiltonian) of Kmxn from which we derive a necessary condition for the existence of a cyclic HCS of Kmxn. Then in Section 4 we give a complete solution to the existence problem of a cyclic HCS with an even number of parts, proving that in this case the necessary condition we found is also sufficient. The main result of this paper is the following.
Theorem 1.1. Let m be even; a cyclic and n-symmetric HCS for Kmxn exists if and only if
(a)	n = 0 (mod 4), or
(b)	n = m = 2 (mod 4).
The proof of Theorem 1.1 will follow from the various results proved in Sections 3 and 4. First, in Corollary 3.4 we give the necessary condition for the existence of a cyclic HCS
F Merola et al.: Cyclic and symmetric hamiltonian cycle systems.
221
of Kmxn. Then, in Proposition 4.2 we study the bipartite case, finally in Theorem 4.3 and in Theorem 4.7 we deal with the case n = 0 (mod 4), and n = 2 (mod 4), respectively.
2 Preliminaries
The main results of this paper will be obtained by using the method of partial differences introduced by Marco Buratti and used in many papers, see for instance [2, 9, 10, 11, 13, 14, 27]. Here we recall some definitions and results useful in the rest of the paper.
Definition 2.1. Let C = (c0, ci,..., q_i) be an ¿'-cycle with vertices in an abelian group G and let d be the order of the stabilizer of C under the natural action of G, that is, d =
|{g g G : C + g = C}|. The multisets
AC = {±(ch+i - ch) | 0 < h<*}, dC = {±(ch+i - ch) | 0 < h < ¿/d},
where the subscripts are taken modulo ¿, are called the list of differences from C and the
list of partial differences from C, respectively.
More generally, given a set B of ¿-cycles with vertices in G, by AB and dB one means the union (counting multiplicities) of all multisets AC and dC respectively, where C g B.
We recall the definition of a Cayley graph on a group G with connection set Q, denoted by Cay [G : Q]. Let G be an additive group and let Q C G \ {0} such that for every w g Q we also have —w g Q. The Cayley graph Cay[G : Q] is the graph whose vertices are the elements of G and in which two vertices are adjacent if and only if their difference is an element of Q (an analogous definition can be given in multiplicative notation). Note that Kmxn can be interpreted as the Cayley graph Cay [Zmn : Zmn \ mZmn], where by mZmn we mean the subgroup of order n of Zmn. The vertices of Kmxn will be always understood as elements of Zmn and the parts of Kmxn are the cosets of mZmn in Zmn. We consider the natural action of Zmn on the cycles of Kmxn: given a cycle C = (c0, c1,..., c^_1) of Kmxn we define C+t as the cycle (c0 +t, c1 +t,..., c^_1 +t), where c0, c1,..., c^_1, t are elements of Zmn. The stabilizer and the orbit of any cycle C of Kmxn will be understood with respect to this action and will be denoted by Stab(C) and Orb(C), respectively. A cyclic HCS of Kmxn is completely determined by a set of base cycles, namely, a complete system of representatives for the orbits of its cycles under the action of Zmn. The next theorem, which is a consequence of the theory of partial differences, will play a fundamental role in this paper.
Theorem 2.2. A set B of mn-cycles is a set of base cycles of a cyclic HCS of Kmxn if and only if dB = Zmn \ mZmn.
In Example 2.4 we will show how to construct a cyclic HCS of K10x6 applying Theorem 2.2.
For our purposes the following notation will be useful. Let c0, c1,..., cr_1, x be elements of an additive group G, with x of order d. The closed trail
[co, c1, c2,..., cr_1, co + x, c1 + x, c2 + x, .. ., cr_1 + x,. .., co + (d — 1)x, c1 + (d — 1)x, c2 + (d — 1)x,. .., cr_1 + (d — 1)x]
222
Ars Math. Contemp. 12 (2017) 383-413
will be denoted by
[co, Cl, . . . , cr_l]x.
For brevity, given P = [c0, c1,..., cr-1], we write [P]x for the closed trail [c0, c1,..., cr-1]x. For instance in Z12 [0,5,1]9 represents the closed trail (a cycle in this case)
(0, 5,1, 9, 2,10, 6,11, 7, 3, 8, 4).
Remark 2.3. Note that [c0, c1,..., cr-1]x is a (dr)-cycle if and only if the elements q, for i = 0,..., r - 1, belong to pairwise distinct cosets of the subgroup (x) in G. Also, if
C = [c0, c1,..., cr-1]x is a (dr)-cycle, then
dC = {±(c - ci-1) | i = 1, .. ., r - 1} U {±(c0 + x - cr-1)}.
We point out that in the case of cyclic HCS of Kmxn we have that dr = mn. Hence, if the list dC has no repeated elements, the order of Stab(C) is d, and the length of the Zmn-orbit of C is r.
Example 2.4. Here we present the construction of a cyclic HCS of K10x6. Consider the following cycles with vertices in Z60:
C1 = [0,19,1,17, 3,15, 6,14, 8,12]10, C2 = [0, 29,1, 28, 2, 27, 3, 26,4, 25]10,
C3 = [0, 3]2, C4 = [0, 7]2, C5 = [0,13]2, C6 = [0] 17.
One can easily check that B = {C1,..., C6} is a set of hamiltonian cycles of K10x6 and that:
dC1 = ±{19,18,16,14,12, 9, 8, 6,4, 2}, dC2 = ±{29, 28, 27, 26, 25, 24, 23, 22, 21,15},
dC3 = ±{3,1}, dC4 = ±{7,5}, dC5 = ±{13,11}, dC6 = ±{17}.
Hence dB = Z60 \ 10Z60. So, in view of Theorem 2.2, we can conclude that B is a set of base cycles of a cyclic HCS of K10x6.
Explicitly the required system consists of the following 27 cycles:
{C1 + i, C2 + i | i = 0, .. ., 9} U {C3 + i, C4 + i, C5 + i | i = 0,1} U {C6}.
An HCS of the complete graph Kv, v odd, is said to be symmetric if there is an invo-lutory permutation ^ of the vertices of Kv fixing all its cycles; in the case v is even, an HCS of the cocktail party graph Kv - I is symmetric if all its cycles are fixed by the involution switching all pairs of endpoints of the edges of I. This definition is due to Akiyama, Kobayashi and Nakamura [1] in the case v odd, and to Brualdi and Schroeder [6] in the case v even. Symmetric hamiltonian cycle systems always exist in the odd case: an example is the well-known Walecki construction, and more generally, any 1-rotational HCS is clearly symmetric (an HCS is called 1-rotational if it has an automorphism group G acting sharply transitively on all but one vertex). It was recently proved that the number of nonisomorphic 1-rotational HCSs of order v = 2n +1 > 9 is bounded below by 2 T3n/41 ([16]), so that in the case v odd symmetric HCSs are quite common. In the case v even we have the following result.
F Merola et al.: Cyclic and symmetric hamiltonian cycle systems.
223
Theorem 2.5 (Brualdi and Schroeder [6]). A symmetric HCS of Kv - I exists if and only if v = 1 or 2 (mod 4).
In [14], the authors study the case of an HCS of Kv which is both cyclic and symmetric; their result in the case v even is that there exists a cyclic and symmetric HCS of Kv for all values for which a cyclic HCS exists, that is, for v = 1 or 2 (mod 4) and | not a prime power.
Very recently Michael Schroeder [23] studied hamiltonian cycle systems for a graph r in which each cycle is fixed by a fixed-point-free automorphism $ of r of order n > 2, so that V(r) = mn for some m; we shall call such an HCS n-symmetric. To admit an n-symmetric HCS, r must be a subgraph of Kmxn, and in [23] the existence problem of an n-symmetric HCS for Kmxn is completely solved in the following result.
Theorem 2.6 (Schroeder [23]). Let m > 2 and n > 1 be integers such that (m - 1)n is even. An n-symmetric HCS for Kmxn always exists except when we have, simultaneously, n = 2 (mod 4) and m = 0 or 3 (mod 4).
Note that we shall see the same non-existence condition later on in Corollary 3.4. It makes sense therefore to study, as done in [14] for the cocktail party graph, hamiltonian cycle systems for the complete multipartite graph that are both cyclic and symmetric. As noted above, Km xn is the Cayley graph Cay [Zmn : Zmn \ mZmn ]. Let y be the morphism x ^ x +1 (mod mn) and set $ = Ym. We have the following condition for a cycle in a cyclic cycle system to be $-invariant.
Lemma 2.7. A cycle C in a cyclic HCS of Kmxn is 4>-invariant if and only if n divides \Stab(C)| - or equivalently, if \Orb(C)| divides mn = m.
Example 2.8. Let us consider once more the cycles we used in Example 2.4; we can easily see that the cycle system is also 6-symmetric, since the length of the orbit is 10 for cycles Ci and C2, 2 for cycles C3,C4, C5 and 1 for C6.
3 Non-existence results
In this section we shall present some non-existence results for cycle systems of the complete multipartite graph Kmxn; the methods used here will be closely related to those used in [15], where the case of the cocktail party graph is considered. The results will concern general cycle systems; we will then apply these results to the hamiltonian case.
The following lemma is an immediate generalization of Lemma 2.1 of [15], hence we omit the proof.
Lemma 3.1. Let C = (c0, c1,..., c£-1) be a cycle belonging to a cyclic cycle system of Kmxn and let d be the order of Stab(C). Then Orb(C) is an ¿-cycle system of Cay [Zmn : {±(ci-i - Ci) | 1 < i < d}].
The next result generalizes Theorem 2.2 of [15].
Proposition 3.2. Let n be an even integer. The number of cycle orbits of odd length in a cyclic cycle decomposition of Kmxn has the same parity of m(m-1)n .
224
Ars Math. Contemp. 12 (2017) 383-413
Proof. Let B be a cyclic cycle system of Kmxn. For every ¿'-cycle C = (c0, c1,..., c£-1) of B set
ijd
°(C) = ^2(ci-i - Ci) = (co - ci) + (ci - C2) + ... + (c^jd-1 - ctjd) = Co - ctjd, i=1
where d is the order of Stab(C). It is easy to see that ce/d = c0 + p where p is an element of Zmn of order d and hence we have
a(C) =	with gcd(x,d) = 1.
Since n is even, we have that a(C) is even if and only if d is a divisor of mp; on the other hand, since the length of Orb(C) is mp, also |Orb(C)| is even if and only if d is a divisor of mp. For any cycle C e B, we thus have that
a(C) = |Orb(C)| (mod 2).	(3.1)
Let S = {C1,... ,Cs} be a set of base cycles of B, that is, a complete system of representatives for the orbits of the cycles of B, so that we have
B = Orb(C1) U Orb(C2) U ... U Orb(Cs).
By Lemma 3.1, the cycles of Orb(Ci) form a cycle system of Cay[Zmn : dCi]. Hence it follows that
s
Cay [Zmn : Zmn \ mZmn] = U Cay [Zmn : dCi] = Cay [Zmn : dS]
i=1
so that we obtain
OS = Zmn \ mZmn.	(3.2)
Note that dCi is a disjoint union of the set of summands of a(Ci) and the set of their additive inverses. Hence, by (3.2), it follows that Zmn \ mZmn is a disjoint union of the set of all summands of the sum J2s=1 a(Ci) and the set of their additive inverses. Then, considering that additive inverses elements have the same parity and that Zmn \ mZmn = ±({1,2,..., m^ - 1} \ {m, 2m,..., (n - 1)m}) we can write:
s	m2-1 n-1
^^a(Cj) = ^^ i - m^^i (mod 2)
i=1 i=1 i=1
and then
From (3.1) we have
t "(Ci) - ^^^ (mod 2).
i=1
tt |Orb(Ci)| =	(mod 2).
i=1
Hence the number of cycles Ci of S whose orbit has odd length has the same parity as m(m-1)n2, and the assertion follows.	□
F Merola et al.: Cyclic and symmetric hamiltonian cycle systems.
225
Now we are ready to prove the main non-existence result. In the following given a positive integer x by |x|2 we will denote the largest e for which 2e divides x.
Theorem 3.3. Let n be an even integer. A cyclic t-cycle system of Kmxn cannot exist in each of the following cases:
(a)	m = 0 (mod 4) and |t|2 = |m|2 + 2|n|2 - 1;
(b)	m = 1 (mod 4) and |t|2 = |m - 1|2 + 2|n|2 - 1;
(c)	m = 2, 3 (mod 4), n = 2 (mod 4) and t ^ 0 (mod 4); or
(d)	m = 2, 3 (mod 4), n = 0 (mod 4) and |t|2 = 2|n|2.
Proof. If B is an t-cycle system of Kmxn, then |B| = |E(Kmxn)|/t = mn2(m - 1)/2t. Hence the number of cycle orbits of odd length of a cyclic t-cycle system of Kmxn has the same parity as mn2(m - 1)/2t. By Proposition 3.2, we have that mn2(m - 1)/2t = mn2(m - 1)/8 (mod 2). Now the conclusion can be easily proved distinguishing four cases according to the congruence class of m modulo 4.	□
If the cycles of the system are hamiltonian, that is if t = mn, we obtain the following corollary.
Corollary 3.4. Let n be an even integer. A cyclic HCS of Kmxn cannot exist if both m = 0, 3 (mod 4) and n = 2 (mod 4).
4 Existence of a cyclic and symmetric HCS of KmXn, m even
In this section we present direct constructions of a cyclic and symmetric HCS of the complete multipartite graph with an even number of parts. Since (m - 1)n must be even, if m is even then n is even too; the condition in Corollary 3.4 tells us that when n = 2 (mod 4), m should also be congruent to 2 modulo 4. If these two requirements are met, we will show that a cyclic and symmetric HCS of Kmxn always exists, and therefore we prove Theorem 1.1.
As observed in the Introduction, Kmx2 = K2m - I is the cocktail party graph; thus we can suppose n > 2, since for n = 2 we can rely on the following result.
Theorem 4.1 (Jordon, Morris [17]; Buratti, Merola [14]). For an even integer v > 4 there exists a cyclic and symmetric HCS of Kv -1 if and only if v = 2,4 (mod 8) and v = 2pa, where p is an odd prime and a > 1.
We start by considering the complete bipartite graph.
Proposition 4.2. For any even integer n there exists a cyclic and n-symmetric HCS of
K2xn.
Proof. For n = 2t we need a set B of base cycles such that dB = ±{1,3,..., 2t - 1}. Let us first assume t even. For i = 0,1,..., t/2 - 1 consider the cycle C, = [0,4i + 3]2. We have BC, = ±{4i + 1,4i + 3}, and thus B = {C0, Cx,..., Q/2-1} is a set of hamiltonian cycles of K2xn such that dB = Z2n \ 2Z2n. Now assume that t is odd. For i = 0,1,..., |_t/2j - 1 take C, = [0,4i + 3]2 as above, and add the cycle C = [0^-1. Now B = {C0, C1,..., CL£/2J-1,C'} is a set of base cycles for a cyclic HCS of K2xn. This cycle system is also n-symmetric by Lemma 2.7 since each cycle belongs to an orbit of length 1 or 2.	□
226
Ars Math. Contemp. 12 (2017) 383-413
Now we tackle the case n = 0 (mod 4).
Theorem 4.3. Let m be an even integer and n = 0 (mod 4). Then there exists a cyclic and n-symmetric HCS of Kmxn.
Proof. We may assume m > 4, since if m = 2, the statement follows from Proposition 4.2. We shall first give a construction for m a power of 2. Let m = 2° and n = 4t with a > 1 and t > 1. We will build a set of a • t base cycles. For all b = 1,..., a and i = 0,..., t — 1 consider the following path:
Pib = [0, 2mi + (2b+1 — 1), 1, 2mi + (2b+1 — 2), 2, 2mi + (2b+1 — 3),..., (2b-1 — 1), 2mi + (2b+1 — 2b-1)].
Note that the elements of Pij6 are pairwise distinct modulo 2b: hence Ai}b = [P^]^ is a hamiltonian cycle of Kmxn. It is straightforward to check that
dAij6 = ±({2mi + 2b-1} U {2mi + (2b + 1), 2mi + (2b + 2),..., 2mi + (2b+1 — 1)}).
Thus U(dAij6) = Zmn \ mZmn, and the existence of a cyclic HCS of Kmxn follows from Theorem 2.2.
Now assume m = 2°m with a > 1 and m > 1 odd. Take n = 4t with t > 1. We start constructing for all i = 0, . . . , t — 1 the following paths:
= , [0, 2mi + (4j — 1)] if j = 1,..., m-1	(41)
Pi'j 1 [0,2mi + (4j + 1)] if j = mi1 ,...,m — 1 .	(4.1)
Since 2mi + (4j — 1) and 2mi + (4j + 1) are odd, Ai,j — [Pi,j]2 is a hamiltonian cycle of Kmx„ for any i, j. Clearly dAij = ±{2mi+(4j — 3), 2mi+(4j — 1)} for j = 1,..., m-1 and 5Aijj = ±{2mi + (4j — 1), 2mi + (4j + 1)} for j = mJ1,..., m — 1. Hence for any fixed i we have
V dAij = ±({2mi + 1, 2mi + 3, 2mi + 5,..., 2mi + (2m — 3)}U
{2mi + (2m + 1), 2mi + (2m + 3), 2mi + (2m + 5), .. ., 2mi + (4m — 3)}). Now for i = 0, . . . , t — 1 consider the paths
Qi,1 = [0, 2mi + (4m — 1), 1, 2mi + (4m — 3), 3, ...,m — 2, 2mi + 3m, (4.2) m + 1, 2mi + (3m — 1), m + 3, 2mi + (3m — 3),.. ., 2m — 2, 2mi + (2m + 2)];
and finally, if a > 2, for all b = 2, . . . , a consider also
Qib = [0, 2mi + (2b+1m — 1), 1, 2mi + (2b+1m — 2), 2,..., (2b-1m — 1), 2mi + (2b+1m — 2b-1m)].
Notice that the elements of Qij6 are pairwise distinct modulo 2bm and hence Bi b = [Qi,6]26m is a hamiltonian cycle of Kmxn for any i = 0,... ,t — 1 and b = 1,..., a.
Also,
dBi1 = ±({2mi + 2, 2mi + 4, 2mi + 6,..., 2mi + 2m — 2} U
{2mi + 2m + 2, 2mi + 2m + 4, 2mi + 2m + 6,. .., 2mi + 4m — 2} U {2mi + 2m — 1, 2mi + 4m — 1})
F Merola et al.: Cyclic and symmetric hamiltonian cycle systems.
227
and for b = 2,..., a
dBij6 = ±({2m« + 2b-1m}U{2mi + (2bm + 1), 2m« + (2bm + 2),..., 2mi + (2b+1m - 1)}).
It turns out that for every fixed i we have
U dBj,5 = ± ({2mi + 2, 2mi + 4, 2mi + 6, .. ., 2mi + 4m}U
{2mi + (4m + 1), 2mi + (4m + 2), 2mi + (4m + 3),. .., 2mi + (m - 1)}U
{2mi + (m + 1), 2mi + (m + 2), 2mi + (m + 3),. .., 2mi + (2m — 1)}).
Let B = {Ajj | 0 < i < t, 1 < j < m} U {Bij6 | 0 < i < t, 1 < b < a}. From what we have seen above, for every fixed i we have
(V dA j U dBj,^ = ±({2mi + 1, 2mi + 2, 2mi + 3,..., 2mi + (m — 1)}U
{2mi + (m + 1), 2mi + (m + 2), 2mi + (m + 3),. .., 2mi + (2m — 1)})
and so dB = Zmn \ mZmn. We conclude that B is a set of base cycles of a cyclic HCS of
K „
It is easily seen from Lemma 2.7 that these cycle systems are also n-symmetric, since in all cases the length of the orbit of each cycle divides m.	□
Example 4.4. Following the proof of Theorem 4.3 we give here the construction of a set of base cycles of a cyclic and 4-symmetric HCS of K18x4. In the notation of the Theorem, a = 1, m = 9 and t =1. Take the following cycles:
Ao,i = [0,3]2, Ao,2 = [0,7]2, AO,3 = [0,11]2, Ao,4 = [0,15]2,
Ao,5 = [0, 21]2, Ao,6 = [0,25]2, Ao,7 = [0,29]2, Ao,8 = [0,3% B0j1 = [0, 35,1, 33, 3, 31, 5, 29, 7, 27,10, 26,12, 24,14, 22,16, 20] 18.
We have
U dAo . = ± ({1, 3, 5,..., 15} U {19, 21, 23,..., 33})
j=1
and
dBo1 = ± ({2,4, 6,..., 16} U {20, 22, 24,..., 34} U {17, 35}).
So, given B = {Aoj1, Ao,2,..., Ao,8, Boj1}, we have dB = Z72 \ 18Z72.
Now, we give the construction of a set of base cycles of a cyclic and 8-symmetric HCS of K72x8. Notice that m = 9 as before, but a = 3 and t = 1, so we need to construct a larger number of cycles. For i = 0 we take
Ao,1 = [0,3]2, Ao,2 = [0,7]2, Ao,3 = [0,11]2, Ao,4 = [0,15]2,
Ao,5 = [0, 21]2, Ao,6 = [0,25]2, Ao,7 = [0,29]2, Ao,8 = [0,33]2,
228
Ars Math. Contemp. 12 (2017) 383-413
B0,i = [0, 35,1, 33, 3, 31, 5, 29, 7, 27,10, 26,12, 24,14, 22,16, 20]i8, B0,2 = [0, 71,1, 70, 2, 69, 3, 68,..., 17, 54]36, B0,3 = [0,143,1,142, 2,141, 3,140,..., 35,108]72.
We have
U dA j u	= ± ({1, 2, 3,..., 71} U {73, 74, 75,..., 143}).
Furthermore, for i = 1:
Ai,i = [0,147] 2, Ai,2 = [0,151]2, Ai,3 = [0,155]2, AM = [0,159]2, Ai,5 = [0,165]2, Ai,6 = [0,169]2, Ai,7 = [0,173]2, Ai,8 = [0,177]2,
Bi i = [0,179,1,177, 3,175, 5,173, 7,171,10,170,12,168,14,166,16,164] i8, Bi,2 = [0, 215,1, 214, 2, 213, 3, 212,..., 17,198]36, Bi,3 = [0, 287,1, 286, 2, 285, 3, 284,..., 35, 252]72.
We have
U dA j u(^U1	= ±({145,146,147,..., 215} U {217, 218, 219,..., 287}).
So, given B = {Aij | i = 0,1, j = 1,..., 8} U {Bj,6 | i = 0,1, b =1,2,3}, we have
dB = Z576 \ 72Z576.
The following definition and lemma are instrumental in proving Theorem 4.7, where we shall settle the case n = 2 (mod 4).
Definition 4.5. For all positive integers s, d and all odd integers w > 3, set
w — 3
S(s, d, w) = | s + id | 0 < i < and
<^>(s,d, w) = |{x € S(s,d, w) : gcd(x,w) = 1}| .
Lemma 4.6. Assume gcd(s, d, w) = 1. If 3 { s when w = 3, then y(s, d, w) > 0.
Proof. If w = 3 then y>(s, d, 3) = 1, since S(s, d, 3) = {s} and 3 \ s. Suppose now w > 5. The assertion is trivial for gcd(s, w) = 1, since s € S(s, d, w). If gcd(s, w) = 1, consider the set T = {p prime : p | w,p \ s} and let x = ^ p (with the usual convention that
pGT
x =1 if T = 0). Since w > 5 and x < w, we have that s + dx € S(s, d, w): we claim that that gcd(s + dx, w) = 1. Note that no prime factor of gcd(s, w) divides d, otherwise we would have gcd(s, d, w) = 1. Let p be any prime divisor of w. By definition of x, p divides either s or x, but not both. So, we have that p divides one summand of s + dx but not both: thus s + dx is coprime with w.	□
F Merola et al.: Cyclic and symmetric hamiltonian cycle systems.
229
Theorem 4.7. Let m, n be integers with m, n = 2 (mod 4). Then there exists a cyclic and n-symmetric HCS of Kmxn.
Proof. In view of Propositions 4.2 and Theorem 4.1 we may assume m = 2m > 2 and n = 4t + 2 > 2. Using the notation of Definition 4.5 take
3m + 2 if m = 2 (mod 8) 3m — 2 if m = 6 (mod 8) '
d = 4m and w = n. Now Lemma 4.6 guarantees that the set S(3m± 2,4m, n) contains an element v = s + 2mK coprime with n, where 0 < k < n--6. It is useful for the following to observe that gcd(v, mn) = 1, as gcd(3m ± 2, m) = 1.
For all i = 0,..., k consider the paths Qit1 as in (4.2) and, if k > 1, for all i = 0,..., k — 1 consider the paths Pi j as in (4.1). As we have seen in Theorem 4.3, Ai ,j = [Pij]2 and Bi = [Qi,1]m are hamiltonian cycles of Kmxn for any i, j. If t > k + 2, for all i = k + 1,...,t — 1, take also the following paths:
P
Qi
We define
[0, (2i + 1)m + (4j - 1)] [0, (2i +1)m + (4j + 1)]
if j = 1,...
if j = ,
m— 1 2
..., m — 1
[0, (2i + 1)m + (4m - 1), 1, (2i + 1)m + (4m - 3), 3,..., m - 2, (2i + 1)m + 3m, m + 1, (2i + 1)m + (3m - 1), m + 3, (2i + 1)m + (3m - 3), .. ., 2m - 2, (2i + 1)m + (2m + 2)].
u = < „
3m+1 if m = 2 (mod 8) if m = 6 (mod 8)
4
3m — 1
and take the paths:

[0, 2mK + (4j - 1)] if j = 1,..., m—1	;
[o, 2mK + (4j + 1)] if j = m+1,..., m - 1 and j = u ;
= [0, (2k + 1)m + (4m — 1), 1, (2k + 1)m + (4m — 2), 2,..., m — 1, (2k + 1)m + 3m].
Now set Cij = [Pij]2, Di = [(Qi]m, Ej = [Rj]2, F = [S]m and G = [0]v: these are all hamiltonian cycles of Kmxn, and we have that for j = 1,..., 1
dCij = ±{(2i + 1)m + (4j — 3), (2i + 1)m + (4j — 1)}
and for j = ,..., m — 1
dCij = ±{(2i + 1)m + (4j - 1), (2i + 1)m + (4j + 1)}.
Also,
dDi
±({(2i + 1)m + 2, (2i + 1)m + 4, (2i + 1)m + 6,. .., (2i + 1)m + +2m - 2} U {(2i + 1)m + 2m + 2, (2i + 1)m + 2m + 4,. .., (2i + 1)m + +4m - 2} U {(2i + 1)m + 2m - 1, (2i + 1)m + 4m - 1});
230
Ars Math. Contemp. 12 (2017) 383-413
moreover, for j = 1,..., m-i
dEj = ±{2mK + (4j - 3), 2mK + (4j - 1)} and for j = m+1,..., m - 1 with j = u
dEj = ±{2mK + (4j - 1), 2mK + (4j + 1)}.
Finally,
dF = ±({(2k + 2)m + 1, (2k + 2)m + 2, ..., (2k + 3)m - 1} U {2mK + 3m}) and dG = ±{v}.
Let B = {Ai,j | 0 < i < k, 1 < j < m} U {B | 0 < i < k} U {Ci,j | k < i < t, 1 < j < m} U {Dj | k < i < t} U {Ej | 1 < j < m, j = u} U {F, G}. It is routine to check that dB = Zmn \ mZmn, hence we conclude that B is a set of base cycles of a cyclic HCS of Kmxn. Once more, it is easily checked using Lemma 2.7 that this cycle system is also n-symmetric, since in all cases the length of the orbit of each cycle divides m.	□
We point out that the base cycles used in Example 2.4 were constructed following the proof of Theorem 4.7. In particular, according to the notation of the theorem we have
Ci = Bo, C2 = F, C3 = Ei, C4 = E2, C5 = E3, C6 = G.
Example 4.8. Here we present a set of base cycles of a cyclic and 14-symmetric HCS of K6xi4. In the notation of Theorem 4.7, m = t = 3 and we choose k =1 and v =19 which is coprime with 6 • 14. Following the proof of the theorem we have to take the following cycles:
Ao,i = [0, 3]2, Ao,2 = [0,9]2, Bo = [0,11,1,9,4, 8]e, Bi = [0, 23,1, 21,4,20]e,
C2,i = [0, 33]2, C2,2 = [0, 39]2, D2 = [0, 41,1, 39, 4, 38]e, Ei = [0,15]2, F = [0, 29,1, 28, 2, 27]6, G = [0]i9.
It follows that
d{A0ji, A0,2} = ±{1, 3, 7, 9}, d{B0, Bi} = ±{2,4, 5, 8,10,11,14,16,17, 20, 22, 23},
d{C2ji, C2,2} = ±{31, 33, 37, 39}, dD2 = ±{32, 34, 35, 38,40, 41},
dEi = ±{13,15}, dF = ±{21, 25, 26, 27, 28, 29}, dG = ±{19}.
So, letting B be the set of the constructed cycles, we have dB = Z84 \ 6Z84.
Now, we give a set of base cycles of a cyclic and 10-symmetric HCS of Ki0x i0. In the notation of Theorem 4.7, m = 5, t = 2 and we choose k =1 and v = 37 which is coprime with 100. We have to take the following cycles:
A0,i = [0,3]2, ^0,2 = [0, 7]2, ^0,3 = [0,1%, ^0,4 = [0,17]2, B0 = [0,19,1,17, 3,15, 6,14, 8,12]i0, Bi = [0, 39,1, 37, 3, 35, 6, 34, 8, 32]i0, Ei = [0, 23]2, E2 = [0, 27]2, E3 = [0, 33]2,
F Merola et al.: Cyclic and symmetric hamiltonian cycle systems.
231
F = [0,49,1, 48, 2, 47, 3, 46, 4,45]i0, G = [0]37.
We have:
U dA0 i = ±{1,3,5, 7,11,13,15,17},
i= 1 '
d{B0, B1} = ±{2, 4, 6, 8, 9,12,14,16,18,19, 22, 24, 26, 28, 29, 32, 34, 36, 38, 39},
U BE, = ±{21, 23, 25, 27, 31, 33},
j=i
dF = ±{35, 41, 42, 43, 44, 45, 46, 47, 48, 49}, dG = ±{37}.
Hence, letting B be the set of the constructed cycles, we have dB = Z100 \ 10Z100.
Acknowledgements
We thank the two anonymous referees for their careful reading of the paper and their many
helpful suggestions.
References
[1]	J. Akiyama, M. Kobayashi and G. Nakamura, Symmetric Hamilton cycle decompositions of the complete graph, J. Combin. Des. 12 (2004), 39-45, doi:10.1002/jcd.10066, http://dx. doi.org/10.1002/jcd.10066.
[2]	A. Benini and A. Pasotti, On the existence of elementary abelian cycle systems, Graphs Combin. 25 (2009), 1-14, doi:10.1007/s00373-008-0826-4, http://dx.doi.org/10.10 07/ s00373-008-0826-4.
[3]	A. Benini and A. Pasotti, Decompositions of complete multipartite graphs via generalized graceful labelings, Australas. J. Combin. 59 (2014), 120-143.
[4]	E. J. Billington, N. J. Cavenagh and B. R. Smith, Path and cycle decompositions of complete equipartite graphs: four parts, Discrete Math. 309 (2009), 3061-3073, doi:10.1016/j.disc.2008. 08.009, http://dx.doi.org/10.1016/j.disc.2008.08.00 9.
[5]	E. J. Billington, N. J. Cavenagh and B. R. Smith, Path and cycle decompositions of complete equipartite graphs: 3 and 5 parts, Discrete Math. 310 (2010), 241-254, doi:10.1016/j.disc.2008. 09.003, http://dx.doi.org/10.1016/j-disc.2008.09.003.
[6]	R. A. Brualdi and M. W. Schroeder, Symmetric Hamilton cycle decompositions of complete graphs minus a 1-factor, J. Combin. Des. 19 (2011), 1-15, doi:10.1002/jcd.20257, http: //dx.doi.org/10.1002/jcd.2 0257.
[7]	D. Bryant, Cycle decompositions of complete graphs, in: Surveys in combinatorics 2007, Cambridge Univ. Press, Cambridge, volume 346 of London Math. Soc. Lecture Note Ser., pp. 67-97, 2007, doi:10.1017/CB09780511666209.004, http://dx.doi.org/10.1017/ CBO9780511666209.004.
[8]	D. Bryant and C. A. Rodger, Cycle decompositions, in: C. J. Colbourn and J. H. Dinitz (eds.), Handbook of combinatorial designs, Chapman & Hall/CRC, Boca Raton, FL, pp. 373-382, 2nd edition, 2007.
[9]	M. Buratti, Rotational k-cycle systems of order v < 3k; another proof of the existence of odd cycle systems, J. Combin. Des. 11 (2003), 433-441, doi:10.1002/jcd.10061, http://dx. doi.org/10.1002/jcd.10061.
232
Ars Math. Contemp. 12 (2017) 383-413
[10]	M. Buratti and A. Del Fra, Existence of cyclic k-cycle systems of the complete graph, Discrete Math 261 (2003), 113-125, doi:10.1016/S0012-365X(02)00463-6, papers on the occasion of the 65th birthday of Alex Rosa, http://dx.doi.org/10.1016/S0012-365X(02) 00463-6.
[11]	M. Buratti and A. Del Fra, Cyclic Hamiltonian cycle systems of the complete graph, Discrete Math. 279 (2004), 107-119, doi:10.1016/S0012-365X(03)00267-X, in honour of Zhu Lie, http://dx.doi.org/10.1016/S0012-365X(03)00267-X.
[12]	M. Buratti and L. Gionfriddo, Strong difference families over arbitrary graphs, J. Com-bin. Des. 16 (2008), 443-461, doi:10.1002/jcd.20201, http://dx.doi.org/10.10 02/ jcd.20201.
[13]	M. Buratti and F. Merola, Dihedral Hamiltonian cycle systems of the cocktail party graph, J. Combin. Des. 21 (2013), 1-23, doi:10.1002/jcd.21311, http://dx.doi.org/10.10 02/ jcd.21311.
[14]	M. Buratti and F. Merola, Hamiltonian cycle systems which are both cyclic and symmetric, J. Combin. Des. 22 (2014), 367-390, doi:10.1002/jcd.21351, http://dx.doi.org/10. 1002/jcd.21351.
[15]	M. Buratti and G. Rinaldi, A non-existence result on cyclic cycle-decompositions of the cocktail party graph, Discrete Math. 309 (2009), 4722-4726, doi:10.1016/j.disc.2008.05.042, http://dx.doi.org/10.1016Zj.disc.2008.05.042.
[16]	M. Buratti, G. Rinaldi and T. Traetta, Some results on 1-rotational Hamiltonian cycle systems, J. Combin. Des. 22 (2014), 231-251, doi:10.1002/jcd.21352, http://dx.doi.org/10. 1002/jcd.21352.
[17]	H. Jordon and J. Morris, Cyclic Hamiltonian cycle systems of the complete graph minus a 1-factor, Discrete Math. 308 (2008), 2440-2449, doi:10.1016/j.disc.2007.05.009, http://dx. doi.org/10.1016/j.disc.2007.05.009.
[18]	R. Laskar and B. Auerbach, On decomposition of r-partite graphs into edge-disjoint Hamilton circuits, Discrete Math. 14 (1976), 265-268.
[19]	R. Peltesohn, Eine Losung der beiden Heffterschen Differenzenprobleme, Compositio Math. 6 (1939), 251-257, http://www.numdam.org/item?id=CM_1939_6_251_0.
[20]	A. Rosa, On cyclic decompositions of the complete graph into (4m + 2)-gons, Matematicko-fyzikalny Casopis 16 (1966), 349-352.
[21]	A. Rosa, On cyclic decompositions of the complete graph into polygons with odd number of edges (slovak), Casopis Pest. Mat. 91 (1966), 53-63.
[22]	A. Rosa, On decompositions of a complete graph into 4n-gons, Mat. Casopis Sloven. Akad. Vied 17 (1967), 242-246.
[23]	M. W. Schroeder, ^-symmetric Hamilton cycle decompositions of graphs, Discrete Math. 338 (2015), 1586-1594, doi:10.1016/j.disc.2015.04.008, http://dx.doi.org/10.1016/ j.disc.2015.04.008.
[24]	B. R. Smith and N. J. Cavenagh, Decomposing complete equipartite graphs into short odd cycles, Electron. J. Combin. 17 (2010), Research Paper 130, 21, http://www. combinatorics.org/Volume_17/Abstracts/v17i1r130.html.
[25]	B. R. Smith and N. J. Cavenagh, Decomposing complete equipartite graphs into short even cycles, J. Combin. Des. 19 (2011), 131-143, doi:10.1002/jcd.20265, http://dx.doi.org/ 10.1002/jcd.202 65.
[26]	A. Vietri, Cyclic k-cycle systems of order 2kn + k: a solution of the last open cases, J. Combin. Des. 12 (2004), 299-310, doi:10.1002/jcd.20002, http://dx.doi.org/10.10 02/ jcd.20002.
F Merola et al.: Cyclic and symmetric hamiltonian cycle systems.
233
[27] S.-L. Wu and M. Buratti, A complete solution to the existence problem for 1-rotational k-cycle systems of kv, Journal of Combinatorial Designs 17 (2009), 283-293, doi:10.1002/jcd.20217, http://dx.doi.org/10.1002/jcd.2 0217.