ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 8 (2015) 1-28
Odd-order Cayley graphs with commutator subgroup of order pq are hamiltonian*
Dave Witte Morris
Department of Mathematics and Computer Science, University of Lethbridge, Lethbridge,
Alberta, T1K3M4, Canada
Received 1 May 2012, accepted 8 August 2013, published online 11 April 2014
We show that if G is a nontrivial, finite group of odd order, whose commutator subgroup [G, G] is cyclic of order pMqv, where p and q are prime, then every connected Cayley graph on G has a hamiltonian cycle.
Keywords: Cayley graph, hamiltonian cycle, commutator subgroup. Math. Subj. Class.: 05C25, 05C45
1 Introduction
It has been conjectured that there is a hamiltonian cycle in every connected Cayley graph on any finite group, but all known results on this problem have very restrictive hypotheses (see [2, 13, 15] for surveys). One approach is to assume that the group is close to being abelian, in the sense that its commutator subgroup is small. This is illustrated by the following theorem that was proved in a series of papers by Marusic [12], Durnberger [3, 4], and Keating-Witte [10]:
Theorem 1.1 (D.Marusic, E.Durnberger, K.Keating, and D.Witte, 1985). If G is a nontrivial, finite group, whose commutator subgroup [G, G] is cyclic of order pM, where p prime and ^ G N, then every connected Cayley graph on G has a hamiltonian cycle.
Under the additional assumption that G has odd order, we extend this theorem, by allowing the order of [G, G] to be the product of two prime-powers:
Theorem 1.2. If G is a nontrivial, finite group of odd order, whose commutator subgroup [G, G] is cyclic of order pMqv, where p and q are prime, and v G N, then every connected Cayley graph on G has a hamiltonian cycle.
*To Dragan Marusic on his 60th birthday.
E-mail address: Dave.Morris@uleth.ca, http://people.uleth.ca/~dave.morris/ (Dave Witte Morris)
Abstract
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
2
Ars Math. Contemp. 8 (2015) 149-162
Remark 1.3. Of course, we would like to prove the conclusion of Theorem 1.2 without the assumption that |G| is odd, or with a weaker assumption on the order of [G, G].
If v < 1, then there is no need to assume that [G, G] is cyclic:
Corollary 1.4. If G is a nontrivial, finite group of odd order, whose commutator subgroup [G, G] has order pq, where p and q are distinct primes, then every connected Cayley graph on G has a hamiltonian cycle.
This yields the following contribution to the ongoing search [11] for hamiltonian cycles in Cayley graphs on groups whose order has few prime factors:
Corollary 1.5. If p and q are distinct primes, then every connected Cayley graph of order 9pq has a hamiltonian cycle.
Here is an outline of the paper. Miscellaneous definitions and preliminary results are collected in Section 2. (Also, Corollaries 1.4 and 1.5 are derived from Theorem 1.2 in §2E.) The paper's main tool is a technique known as "Marusic's Method." A straightforward application of this method is given in Section 3, and some other consequences are in Section 4. The proof of Theorem 1.2 is in Section 5, except that one troublesome case is postponed to Section 6.
Acknowledgments. I thank D. Marusic for suggesting this research problem. I also thank him, K. Kutnar, and other members of the Faculty of Mathematics, Natural Sciences, and Information Technologies of the University of Primorska (Koper, Slovenia), for their excellent hospitality that supported the early stages of this work. Furthermore, I am grateful to an anonymous referee for helpful comments on an earlier version of this manuscript.
2 Preliminaries
2A Assumptions, definitions, and notation
Assumption 2.1.
(1)	G is always a finite group.
(2)	S is a generating set for G.
Definition 2.2. The Cayley graph Cay(G; S) is the graph whose vertex set is G, with an edge from g to gs and an edge from g to gs-1, for every g G G and s G S.
Notation 2.3.
•	We let G' = [G, G] and G = G/G'. Also, for g g G, we let g = gG' be the image of g in G.
•	For g, h G G, we let gh = h-1gh and [g, h] = g-1h-1 gh.
•	If H is an abelian subgroup of G and k g Z, we let
Hk = { hk | h G H }. This is a subgroup of H (because H is abelian).
D. Witte Morris: Odd-order Cayley graphs with commutator subgroup of order pq...	3
Notation 2.4. For g G G and s1;..., sn G S U S 1, we use [g](s1;..., sn) to denote the walk in Cay(G; S) that visits (in order), the vertices
g, gsi, gSlS2, gSlS2S3, . . . , gSlS2 • • • Sn. We often write (s1,...,sn) for [e](s1,..., sn).
Definition 2.5. Suppose
•	N is a normal subgroup of G, and
•	C = (si)n=1 is a hamiltonian cycle in Cay(G/N; S).
The voltage of C is f]"=1 Sj. This is an element of N, and it may be denoted nC. Remark2.6. If C = [g](s1,..., s„), and N is abelian, then n™=1 Si = (nC)g. Proof. There is some i with (s1s2 • • • s^)g G N. Then
C = (s£+1, S£+2, . . . , Sn, S1, S2, . . . , S^),
so
(nC)g = g-1(s£+1S£+2 • • • Sn S1S2 • • • S£)g
= [(S1S2 • • • S£)g] 1 (S1S2 • • • S£)(S£+1S£+2 • • • Sn) [(S1S2 • • • S£)g] = (S1S2 ••• Sn)<sis2'-'s')g
= S1S2 • • • Sn.	□
2B Factor Group Lemma and Marusic's Method Lemma 2.7 ("Factor Group Lemma" [15, §2.2]). Suppose
•	N is a cyclic, normal subgroup of G,
•	(Si)m=1 is a hamiltonian cycle in Cay(G/N; S), and
•	the product s1s2 • • • Sm generates N.
Then (s1; s2, ..., sm)|N 1 is a hamiltonian cycle in Cay(G; S).
The following simple observation allows us to assume |N| is square-free whenever we apply the Factor Group Lemma (2.7).
Lemma 2.8 ([10, Lem. 3.2]). Suppose
•	N is a cyclic, normal subgroup of G,
•	N = N/$ is the maximal quotient of N that has square-free order,
•	G = G/$,
•	(s1, s2,..., sm) is a hamiltonian cycle in Cay(G/N; S), and
•	the product s^ s^ • • • ^ generates N.
Then s1s2 • • • sm generates N, so (s1; s2, ..., sm)|N 1 is a hamiltonian cycle in Cay(G; S).
4
Ars Math. Contemp. 8 (2015) 149-162
Remark 2.9 (cf. [7, Thm. 5.1.1]). When applying Lemma 2.8, it is sometimes helpful to know that if
•	N, N = N/$, and G = G/$ are as in Lemma 2.8, and
•	S is a minimal generating set of G.
Then S is a minimal generating set of G.
Lemma 2.10 ("Marusic's Method" [12], cf. [10, Lem. 3.1]). Suppose
•	So C S,
•	(S0) contains G',
•	there are hamiltonian cycles Gi,..., Gr in Cay((S0)/G'; S0) that all have an oriented edge in common, and
•	for every 7 G G', there is some i, such that (7 • nG^ = G'.
Then there is a hamiltonian cycle in Cay(G/G'; S) whose voltage generates G'. Hence, the Factor Group Lemma (2.7) provides a hamiltonian cycle in Cay(G; S).
Corollary 2.11. Assume G' = Zp x Zq, where p and q are distinct primes. Then, in the situation of Marusic's Method (2.10), the final condition (*) can be replaced with either of the following:
(1)	r = 3, and ((nGj)-1 (nGj)) = G' whenever 1 < i < j < 3.
(2)	r = 4, and
•	((nCi)-1 (nC2)) contains Zp, and
•	((nci)-1(nc3)) = ((nG2)-1(nG4)) = Zq.
Proof. Let 7 G G'.
(1)	Consider the three elements 7 •nG1,7 ^G2, and 7 •nG3 of Zp xZq. By assumption, no two have the same projection to Zp, so only one of them can have trivial projection. Similarly for the projection to Zq. Therefore, there is some i, such that 7 • nGj projects nontrivially to both Zp and Zq. Therefore (7 • nGj) = G'.
(2)	There is some i G {1, 2}, such that 7 • nGj projects nontrivially to Zp. We may assume the projection of 7 • nGj to Zq is trivial (otherwise, we have (7 • nGj) = G', as desired). Then 7 • nGj+2 has the same (nontrivial) projection to Zp, but has a different (hence, nontrivial) projection to Zq. So (7 • nGj+2) = G'.	□
2C Some known results
We recall a few results that provide hamiltonian cycles in Cay(G; S) under certain assumptions.
Theorem 2.12 (Witte [14]). If |G| = pM, wherep is prime and ^ > 0, then every connected Cayley digraph on G has a directed hamiltonian cycle.
Theorem 2.13 (Ghaderpour-Morris [6]). If G is a nontrivial, nilpotent, finite group, and the commutator subgroup of G is cyclic, then every connected Cayley graph on G has a hamiltonian cycle.
D. Witte Morris: Odd-order Cayley graphs with commutator subgroup of order pq...	5
Theorem 2.14 (Ghaderpour-Morris [5]). If |G| = 27p, where p is prime, then every connected Cayley graph on G has a hamiltonian cycle.
The proof of the preceding theorem has the following consequence.
Corollary 2.15. If G is a finite group, such that |G/G'| = 9 and G' is cyclic of order pM • 3V, where p > 5 is prime, then every connected Cayley graph on G has a hamiltonian cycle.
Proof. Let G = G/(G')3p. Then |G| = 27p and |G'| = 3p, so the proof of [5, Props. 3.4 and 3.6] provides a hamiltonian cycle in Cay (G/G'; S) whose voltage generates G'. Then Lemma 2.8 provides a hamiltonian cycle in Cay(G; S).	□
Theorem 2.16 (Alspach [1, Thm. 3.7]). Suppose
•	s € S,
•	(s) <G,
•	|G/(s)| is odd, and
•	there is a hamiltonian cycle in Cay (G/ (s); S).
Then there is a hamiltonian cycle in Cay(G; S).
This has the following immediate consequence, since every subgroup of a cyclic, normal subgroup is normal:
Corollary 2.17. Suppose
•	G' is cyclic,
•	s € S n G',
•	|G/(s)| is odd, and
•	there is a hamiltonian cycle in Cay(G/ (s); S). Then there is a hamiltonian cycle in Cay(G; S).
2D Group theoretic preliminaries
We recall a few elementary facts about finite groups.
Lemma 2.18 ([6, Lem. 3.4]). Suppose
•	(a, b) = G,
•	G' is cyclic of square-free order, and
•	G' C Z(G).
Then | [a, b] | is a divisor of both (a) and |G/ (a)|.
Lemma 2.19 ([6, Lem. 3.5]). If G = (a, b), and G' is cyclic, then G' = ([a, b]).
Corollary 2.20. Suppose
•	(a, G') = G, and
•	G' is cyclic of square-free order.
6
Ars Math. Contemp. 8 (2015) 149-162
Then a does not centralize any nontrivial subgroup of G'.
Proof. Let 7 be a generator of the cyclic group G', and let G = G/ ([a, 7]), so a centralizes 7. Then G' = (7) C Z(G), so Lemma 2.18 tells us that |G'| = |[a, 7] is a divisor of |G/(a)| = 1. This means G is abelian, so ([a, 7]) = G' = (7). This implies that a does not centralize any nontrivial power of 7. In other words, a does not centralize any nontrivial subgroup of G'.	□
Lemma 2.21. Suppose
•	G' = Z3m is cyclic of order 3M, for some m G N, and
•	G/ (G')3 is a nonabelian group of order 27.
Then
(1)	m =1 (so |G| = 27),
(2)	(ab)3 = a3b3 for all a, b G G, and
(3)	the elements of order 3 (together with e) form a subgroup of G.
Proof. Note that |G| = 3M+2, so G is a 3-group. Since G' is cyclic (and 3 is odd), it is not difficult to show
(ab)3 G a3b3(G')3, for all a, b G G.	(2.21A)
(This is a special case of [9, Satz III.10.2(c), p. 322].)
(1)	Since G/G' = Z3 x Z3, there is a 2-element generating set {a, b} of G. (In fact, every minimal generating set has exactly two elements [9, 3.15, p. 273].) Since a3, b3 G G', we see from (2.21A) that we may assume b3 G (G')3 (by replacing b with ba or ba-1, if necessary). Furthermore, by modding out (G')9, there is no harm in assuming m < 2, so (G')3 C Z(G). Therefore [a, b3] = e, so [9, Satz 10.6(b), p. 326] tells us that [a, b]3 = e. Since ([a, b]) = G' (see Lemma 2.19), this implies m =1.
(2)	Since m = 1, we have (G')3 = {e}, so this is immediate from (2.21A).
(3)	This is immediate from (2). (Also, it is a special case of [9, Satz III.10.6(a), p. 326].)
□
2E Proofs of Corollaries 1.4 and 1.5
Proof of Corollary 1.4. Assume, without loss of generality, that p < q. Then Sylow's Theorem implies that G' has a unique Sylow q-subgroup Q, so Q < G. Therefore G acts on Q by conjugation. Since Q = Zq, we know that the automorphism group of Q is abelian (more precisely, it is cyclic of order q - 1), so this implies that G' centralizes Q. So Q C Z(G'). Since G'/Q is cyclic (indeed, it is of prime order, namely, p), this implies that G' is abelian. Since p = q, we know that every abelian group of order pq is cyclic, so we conclude that G' is cyclic. Therefore Theorem 1.2 applies.	□
Proof of Corollary 1.5. Assume |G| = 9pq. We may assume p and q are odd, for otherwise |G| is of the form 18p, so [11, Prop. 9.1] applies. Therefore |G| is odd, so it suffices to show |G'| is a divisor of pq, for then Corollary 1.4 (or Theorem 1.1) applies.
Note that we may assume 3 G {p, q}, for otherwise |G| is of the form 27p, so Theorem 2.14 applies. Therefore, neither |Aut(Z9)| = 6 nor |Aut(Z3 x Z3)| =48 is divisible
D. Witte Morris: Odd-order Cayley graphs with commutator subgroup of order pq...
7
by either p or q, so Burnside's Transfer Theorem [7, Thm. 7.4.3, p. 252] implies that G has a normal subgroup N of order pq. Since |G/N| = 9, and every group of order 9 is abelian, we know that G' C N, so |G'| is a divisor of |N | = pq, as desired.	□
Let us also record the fact that almost all cases of Theorem 1.2 will be proved by using Marusic's Method (2.10):
Theorem 2.22. Assume
•	S is a minimal generating set for a nontrivial, finite group G of odd order,
•	G' is cyclic of order pMqv, where p and q are prime, and v G N,
•	for all s G S, we have s G G' and G' C (s},
•	G/(G')3 is not the nonabelian group of order 27 and exponent 3, and
•	either G/G' ^ Z3 x Z3, or #S = 2.
Then, for every y G G', there exists a hamiltonian cycle C in Cay(G/G'; S), such that YnC generates G'.
3 The usual application of Marusic's Method
Applying Marusic's Method (2.10) requires the existence of more than one hamiltonian cycle in a quotient of Cay(G; S). In practice, one usually starts with a single hamiltonian cycle and modifies it in various ways to obtain the others that are needed. The following result describes a modification that will be used repeatedly in the proof of Theorem 1.2.
Lemma 3.1 (cf. Durnberger [3] andMarusic [12]). Assume:
•	Co is an oriented hamiltonian cycle in Cay(G; S),
•	a, b G S±1, g G G, and m G Z+,
•	C0 contains:
o the oriented path [ga_(m+1)](am, b, a_m), and o either the oriented edge [g](b) or the oriented edge [gb](b-1).
Then there are hamiltonian cycles C0, C1,..., Cm in Cay(G; S), such that
1/ttC )V _ I [ak,b-1] [ak,b-1]a if Co contains [g](b),
~ 1 [b-1, ak] [ak ,b-1]a if C0 contains [gb](b-1).
(nCo)-1(nCfc ^	,u , o
Proof. Note that [ga_(m+1)](am, b, a_m) contains the subpath [ga_(fc+1)](afc, b, a_k) for 0 < k < m.
Case 1. Assume that C0 contains [g](b). Construct Ck by:
•	replacing the oriented edge [g](b) with the oriented path [g](a_k, b, ak), and
•	replacing the oriented path [ga_(k+1)](ak, b, a_k) with the oriented edge
[ga_(k+1)](b)
8
Ars Math. Contemp. 8 (2015) 149-162
ga
-(m+l)
gba 1 gby
ga-L r

gba
-(m+l)
qa
r
ga
9h
Figure 1: A portion of the hamiltonian cycles C0 (top) and Ck (bottom).
(see Figure 1).
To calculate the voltage of Ck, write C0 = [g](s1;..., sn). There is some I with
si • • • ~se = a-1, so
Ck = [g](a-k, b, ak, (Si)fz2fc, b, (Si^+k+s).
For convenience, let
h = J^J si = I J^J si I = a (mod G'). ¿=£+1 \i=1 /
Then, from Remark 2.6 (and the fact that G' is commutative), we have
(nCk)S = (a-kbak) f] sJ b JJ ;
\i=2 / \i=£+k+2
(a-kbakb-1) ^ si a-kbakb-1 ^ si
\i=£+1
= [ak,b-1] m s^ J] sA • [ak,b-1]h
\i=1 / \i=£+1 J
= [ak,b-1] • (nC0)g • [ak,b-1]a
[a , b ] •	• [a
(nC0)g • [ak,b-1] [ak,b-1]a.
Case 2. Assume that C0 contains [gb](b 1). This is similar. Construct Ck by:
• replacing the oriented edge [gb](b-1) with the oriented path [gb](a-k, b-1, ak), and
k
g
1
D. Witte Morris: Odd-order Cayley graphs with commutator subgroup of order pq...	9
• replacing the oriented path [ga (k+1)](ak, b, a k) with the oriented edge
[ga-(fc+1)](6).
(See Figure 1, but reverse the orientation of the paths in the right half of the figure.)
To calculate the voltage of Ck, write C0 = [gb](s1;..., sn). There is some I with
si • • • se = ab , so
Ck = [gb] (a-k, b-1, ak, (s^, b, (si)n=i+k+2). For convenience, let
h = n si = m sj = ab (modG').
i=£+1 \i=1 J
Then
(e-k \ / n
n * m n si
i=2 ) \i=e+k+2
= (a-kb-1 akb) m sJ a-kbakb-1 JJ si \i=1 /	\i=e+1 J
= b-1(ba-kb-1ak)b • m ( n sj • [ak,b-1]h \i=1 / \i=e+1 J
= [b-1, ak]b • (nCo)gb • [ak,b-1]a6
= (nCo)gb • [b-1, ak]b [ak, b-1]a6.	□
Remark 3.2. In the situation of Lemma 3.1, we have ^(nCo)-1(nCk = ([ak ,b-1]) if either
(1)	C0 contains [g](b) and a does not invert any nontrivial element of ([ak, b-1]), or
(2)	C0 contains [gb](b-1) and a does not centralize any nontrivial element of ([ak,b-1]).
Note that if |G| is odd, then the hypothesis on a in (1) is automatically satisfied (because no element of odd order can ever invert a nontrivial element).
Corollary 3.3 (cf. [4, Case iv] and [10, Case 4.3]). Assume
•	a € S with (a) = G,
•	(si)d=1 is a hamiltonian cycle in Cay(G/(a); S),
•	ar nd=1 si € G', with 0 < r < |a| - 2, and
•	0 < k < |a| - 3.
Then the walk
Ck = (ak,s1,a-(k+1), (s2i,a|a|-2,s2i+1,a-(|a|-2))(=-3)/2,
sd-1, ar, sd, a-( 1 a| -k-2), s1, a 1 a 1 -k-3, (si^, a-( 1 a 1 -r-2), sd)
10
Ars Math. Contemp. 8 (2015) 149-162
is a hamiltonian cycle in Cay(G; S) (see Figure 2), and we have
nck = (nCo)[a-k ,s-1][a-k ,s-1]°-1.
Proof. Co contains the oriented edge (si) and the oriented path [a |a|-2](a-(|a|-3), si,
a|a|-3), so we may apply Lemma 3.1 with g = e, b = s1, and a-1 in the role of a. □ ___
a gd-1
a~lgd-2
a xg2
a
Figure 2: A hamiltonian cycle Ck in Cay(G; S), where gj = f]j=1 sj.
4 Other applications of Marusic's Method
Here are some other situations in which we can apply Marusic's Method (2.10).
Theorem 4.1 ([10, §4 and §5]). Suppose
•	|G| is odd,
•	G = Zp^ is cyclic of prime-power order,
•	S is a generating set of G,
•	S n G = 0, and
•	G is not the nonabelian group of order 27 with exponent 3.
Then there exist hamiltonian cycles C1 and C2 in Cay(G/G'; S) that have an oriented edge in common, such that (nC1)-1(nC2) generates G'.
Proof. Lemma 2.8 allows us to assume |G'| = p. Then the desired conclusion is implicit in [10, §4 and §5] unless |G/G'| = Z3 x Z3 andp = 3.
Therefore G/(G')3 is a nonabelian group of order 27, so Lemma 2.21(1) tells us |G| = 27. By assumption, the exponent of G is greater than 3, so we conclude from
D. Witte Morris: Odd-order Cayley graphs with commutator subgroup of order pq...	11
Lemma 2.21(3) that S contains an element b with |b| > 9. We may assume S is minimal, so #S = 2; write S = {a, b}. Then we have the following two hamiltonian cycles in
Cay(G; S):
C = (a2, b)3 and C2 = (a2,b-1)3.
Since Lemma 2.21(2) tells us (xy)3 = x3y3 for all x,y G G, and we have x3 G G' = Z(G) for all x g G, we see that
(nCi)-1(nC2) = ((a2b)3)-1(a2b-1)3 = ((a2)3b3)-1((a2)3(b-1)3) = b-6 = e,
since |b| > 9.	□
We will use the following version of this result in Subcase ii of Case 5.12.
Proposition 4.2. Suppose
•	|G| is odd,
•	G' = Zp has prime order,
•	Z is a subgroup of Z(G),
•	S n G'Z = 0, and
•	G is not nilpotent.
Then there exist hamiltonian cycles C1 and C2 in Cay(G/(G'Z); S) that have an oriented edge in common, such that ((nC1)-1(nC2)) = G'.
Proof. Choose a, b G S with [a, b] = e. Since G is not nilpotent, we may assume a does not centralize G'. Furthermore, since we are using Marusic's Method (2.10), there is no harm in assuming S = {a, b}.
If b G (a, G', Z}, then the proof of [10, Case 5.3] provides two hamiltonian cycles C1 = (Si)n=1 and C2 = (ti)n=1 in Cay(G/(G'Z); a, b), such that nC = nC2 (and the two cycles have an oriented edge in common). From the construction, it is clear that (si)"=1 is a permutation of (ti)n=1, so (nC0-1(nC2) G G'.
We may now assume b G (a, G', Z}. Then, letting n = |G : (a, G', Z}|, there is some i, such that bi G aiG'Z and 0 < i < n. Therefore, we have the following two hamiltonian cycles in Cay(G/(G'Z); S) that both contain the oriented edge (b):
C1 = (b, a-(i-1),b,an-i-1),
C2 = (b, an-i-1,b,a-(i-1)) = [a-1]C1.
The sequence of edges in C2 is a permutation of the sequence of edges in C1, therefore (nC1)-1(nC2) G G'. Also, since a does not centralize G', it is not difficult to see that (nC1)-1(nC2) is nontrivial, and therefore generates G'.	□
Lemma 4.3. Assume
•	G = Zp^ x Zqv, where p and q are prime,
•	S n G' = 0,
•	there exist a, b G S U S-1, with a = b, such that aG' = bG',
12
Ars Math. Contemp. 8 (2015) 149-162
•	the generating set S is minimal, and
•	|G| is odd.
Then there is a hamiltonian cycle in Cay(G; S). Proof. Write b = 07, with 7 G G'.
Case 1. Assume (7} = G'. We apply Marusic's Method (2.10), so Lemma 2.8 allows us to assum e G' = Zp x Zq. Since |a| > 3, it is easy to find an oriented hamiltonian cycle C0 in Cay(G; S) that has (at least) 2 oriented edges a and a2 that are labeled a. We construct two more hamiltonian cycles Gi and C2 by replacing one or both of a and a2 with a b-edge. (Replace one a-edge to obtain G1; replace both to obtain C2.) Then there are conjugates y1 and y2 of 7, such that
(nCo)-1(nCi) = 71, (nGi)-1(nG2) = 72, (nCo)-1^) = 7172.
By the assumption of this case, we know that y1 and y2 generate G'. Also, since |G| is odd, we know that no element of G inverts any nontrivial element of G', so y1 y2 also generates G'. Therefore, Marusic's Method 2.11(1) applies.
Case 2. Assume (7} = G'. Since S is minimal, we know (7} contains either Zp^ or Zqv. By the assumption of this case, we know it does not contain both. So let us assume (7} = N x Zqv, where N is a proper subgroup of Zp^.
Assume, for the moment, that G/(G')p is not the nonabelian group of order 27 and exponent 3. We use Marusic's Method (2.10), so Lemma 2.8 allows us to assume G' = Zp x Zq. Applying Theorem 4.1 to G/Zq provides us with hamiltonian cycles C1 and C2 in Cay(G/G'; S \ jb}), such that ((nC1)-1(nC2)) contains Zp. (Furthermore, the two cycles have an oriented edge in common.) Since S is a minimal generating set, we know that Cj contains an edge labelled a±1. (In fact, more than one, so we can take one that is not the edge in common with the other cycle.) Assume, without loss of generality, that (t is labelled a. Replacing this edge with b results in a hamiltonian cycle Cj, such that ((nCi)-1(nCj)) = (7} = Zq. Then Marusic's Method 2.11(2) applies.
We may now assume that G/(G')p is the nonabelian group of order 27 and exponent 3. Then G/ (7} is a 3-group, so Theorem 2.12 )ells us there is a directed hamiltonian cycle C0 in the Cayley digraph Cay(G/ (7}; S \ jb}). Since S \ jb} is a minimal generating set of G/(7}, there must be at least two edges a1 and a2 that are labeled a in C. Now the proof of Case 1 applies (but with (7} in the place of G').	□
5 Proof of Theorem 1.2
Assumption 5.1. We always assume:
(1)	The generating set S is minimal.
(2)	S n G' = 0 (see Corollary 2.17).
(3)	p and q are distinct (see Theorem 1.1).
(4)	G is not nilpotent (see Theorem 2.13). This implies G/(G')pq is not nilpotent [9, Satz 3.5, p. 270].
(5)	There do not exist a, b G S U S-1 with a = b and aG' = bG' (see Lemma 4.3).
(6)	There does not exist s G S, such that G' C (s} (see Theorem 2.16).
D. Witte Morris: Odd-order Cayley graphs with commutator subgroup of order pq...	13
Remark 5.2. We consider several cases that are exhaustive up to permutations of the variables a, b, and c, and interchanging p and q. Here is an outline of the cases:
•	There exist a, b e S, such that ([a, bj) = G'.
(5.3)	b e (a).
(5.4)	b e (a) and |a| > 5.
(5.5)	|a| = |b| = 3 and (a) = (b).
•	There exist a, b, c e S, such that Zp^ C ([a, bj) and Zqv C ([a, cj).
(5.7)	b,c e (a).
(5.8)	(a) C (a,b) C (a,b,c).
(5.9)	a centralizes G'/(G')pq.
(5.10)	b,c e (a).
(5.11)	c e (a) and b e (a).
•	There do not exist a, b, c e S, such that ([a, bj, [a, cj) = G'. (5.12)
Case 5.3. Assume there exist a, b e S, such that ([a, bj) = G' and b e (a).
Proof. We use Marusic's Method (2.11), so there is no harm in assuming S = {a, b}. Then (a) = (a, b) = G. Furthermore, Lemma 2.8 allows us to assume G' — Zpq. Let
n = |a| = |G|, fix k with b = ak, and choose 7 e G', such that b = ak7. Note that
•	an = e (since Corollary 2.20 implies that a cannot centralize a nontrivial subgroup of G'), and
•	(7) = G' (since (a) x (7) = (a, b) = G).
We may assume 1 < k < n/2, by replacing b with its inverse if necessary. We may also assume n > 5 (otherwise, we must have k =1, contrary to Assumption 5.1(5)). Therefore
n - k - 2 > 0.
We have the following three hamiltonian cycles in Cay(G; a, b): Ci = (an), C2 = (an-fc-1,b,a-(fc-1),b), C3 = (an-k-2, b, a-(k-1), b, a). Their voltages are
nc1 = an = e,
nC2 = an-fc-1ba-(fc-1)b = an-fc-1(afc7)a-(k-1)(ak7) = an • a-17a7 = 7a7, nCs = an-fc-2ba-(fc-1)ba = a-1(an-fc-1ba-(fc-1) b)a = (nC2)a.
Since |G| is odd, we know that a does not invert Zp or Zq. Therefore nC2 generates G'. Hence, the conjugate nC3 must also generate G'. Furthermore, as was mentioned above, we know that a does not centralize any nontrivial element of G', so (nC2)(nC3)-1 also generates G'. (Also note that all three hamiltonian cycles contain the oriented edge (a).) Hence, Marusic's Method 2.11(1) applies.	□
Case 5.4. Assume there exist a, b e S, such that ([a, bj) = G' and be (a). Also assume
|a| > 5.
14
Ars Math. Contemp. 8 (2015) 149-162
Proof (cf. proof of [10, Case 4.3]). We use Marusic's Method (2.11), so there is no harm in assuming S — {a, b}. Furthermore, Lemma 2.8 allows us to assume G' — Zpq. Let
d — |G/(a)|, so there is some r with b ar — e and 0 < r < |a|. We may assume r < |a| — 2, by replacing b with its inverse if necessary.
Applying Corollary 3.3 to the hamiltonian cycle (b-d) yields hamiltonian cycles C0, Gi, and C2 (since 2 — 5 — 3 < |a| — 3). Note that all of these contain the oriented edge b(b-1). Furthermore, the voltage of Gk is
nCk — n[a-k,b] [a-k,b]2-,
where n — nG0 is independent of k.
Since [a-1, b] generates G', and a does not invert any nontrivial element of G' (recall that |G| is odd), it is easy to see that G' is generated by the difference of any two of
e, [a-1, b], and [a-2, b] — [a-1, b][a-1, b]2-.
Using again the fact that a does not invert any element of G', this implies that G' is generated by the difference of any two of the three voltages, so Marusic's Method 2.11(1) applies.	□
Case 5.5. Assume there exist a, b G S, such that ([a, b]) — G', |a| — |b| — 3 and (a) — (b). Proof. This proof is rather lengthy. It can be found in Section 6.	□
Assumption 5.6. Henceforth, we assume there do not exist a, b G S U S-1, such that
([a, b]) — G'.
Case 5.7. Assume Zp^ C ([a, b]), Zqv C ([a, c]), and (b, c) C (a).
Proof. We use Marusic's Method (2.11), so there is no harm in assuming S — {a, b, c}. (Furthermore, Lemma 2.8 allows us to assume G' — Zpq, so ([a, b]) — Zp and ([a, c]) — Zq.) Then, since b, c G (a), we must have (a) — G. Therefore, Corollary 2.20 tells us that a does not centralize any nonidentity element of G'. Fix k and i with b — ak and c — a£. We may write b — ak y1 and c — a£Y2, for some y1 g Zp and y2 g Yq.
Since 1, k, and i are distinct (see Assumption 5.1(5)), we may assume 1 < k < i < n/2, by interchanging b and c and/or replacing b and/or c with its inverse if necessary. Therefore i > 3 and k + i < n — 2, so we have the following three hamiltonian cycles in Cay(G; a, b, c):
C1 — (a-n)
C2 — (a-(£-1),c, b,a-(k-1),b, an-k-£-2, c) C3 — (a-(£-2),c, b,a-(k-1),b, an-k-£-2, c,a-1).
Note that each of these contains the oriented edge (a-1).
Since a does not centralize any nonidentity element of G', we know nC1 — e. A straightforward calculation shows
nC2 — (71Y?-1 r-fc-1 (72°-172),
which generates G'. Therefore, nG3 — (nC2)2 1 and (nG2)-1(nG3) also generate G'. (For the latter, note that a-1 does not centralize any nonidentity element of G'.) Therefore Marusic's Method 2.11(1) applies.	□
D. Witte Morris: Odd-order Cayley graphs with commutator subgroup of order pq...	15
Figure 3: A hamiltonian cycle X.
e
Case 5.8. Assume C ([a, 6]}, Zqv C ([a, cj), and there exists s G {a, 6}, such that
(a) C (a, s) C (a, 6, c).
Proof. We use Marusic's Method (2.11), so there is no harm in assuming S = {a, 6, c}. Furthermore, Lemma 2.8 allows us to assume G' = Zpq, so ([a, 6]} = Zp and ([a, cj) = Zq. Choose A, B, C > 3, such that aA = e, and every element of G can be written uniquely in the form
0 < x < A, ax6y cz with 0 < y < B, 0 < z < C.
More precisely, we may let
i A = |a|, B = |(a, 6) : (a)|, C = |G : (a, 6)| if s = 6, \ A = |a|, C = |(a,c) : (a)|, B = |G : (a,c)| if s = c.
Then we have the following hamiltonian cycle X in Cay(G; a, 6, c) (see Figure 3):
X = [a,(aA-2, (6, a-(A-1), 6, aA-1)
(a-(A-1), 6-1, aA-1, 6-1)(B-1)/2, a-(A-2), cj 6, a-1, 6B-2, a, (aA-2, 6-1, a-(A-2), 6-1)(B-3)/2, aA-2,6-1 ,a-(A-3),6-1,aA-2,c-(C-1)
,a - 6, a" 0(B-1)/2,c,
,(C-1)/2
a ^,6 "a"
We obtain a new hamiltonian cycle Xp by replacing a subpath of the form [g] (aA 1, 6, a-(A-1)) with [g](a-(A-1) ,6,aA-1). Then (nX )-1(nXp) is a conjugate of
(aA-16a-(A-1))-1(a-(A-1)6aA-1) = [6, aA-1]°[6, aA-1j.
Similarly, replacing a subpath of the form [g](aA-1, c, a-(A-1)) with [g](a-(A-1),c, aA-1) results in a hamiltonian cycle Xq, such that (nX)-1(nXq) is a conjugate of [c, aA-1]°[c, aA-1j. Furthermore, doing both replacements results in a hamiltonian cycle Xp, such that (nXp)-1 (nXp) is also a conjugate of [c, aA-1f[c, aA-1]. Note that all four of these hamiltonian cycles contain the oriented edge c(c-1).
Since G' C (a) (see Assumption 5.1(6)), we may assume aA G Zp (by interchanging p and q if necessary). Since [c, a] G Zq, this implies that c centralizes aA, so [c, aA-1] =
16
Ars Math. Contemp. 8 (2015) 149-162
Figure 4: A hamiltonian cycle Y1.
e
(C-1)/2
[c, a-1] generates Zq. Since a does not invert any nontrivial element of Z (recall that G has odd order), this implies that [c, aA-1]°[c, aA-1] generates Zq.
Assume, for the moment, that [b, aA-1] generates Zp. Since a does not invert any nontrivial element of Zp, this implies that [b, aA-1]°[b, aA-1] generates Zp. Therefore, Marusic's Method 2.11(2) applies.
We may now assume [b, aA-1] does not generate Zp. This means [b, aA-1] = e. Since [b, a-1] = e, we conclude that [b, aA] = e, so
b does not centralize Zp.
We have the following hamiltonian cycle Y1 in Cay(G; a, b, c) (see Figure 4):
Y1 = (b, (bB-3, (a, b-(B-2), a, bB-2)(A-1)/2, b, a-(A-1), c,
aA-1, b-1, (b-(B-2), a-1, bB-2, a-1)(A-1)/2, b-(B-3), c)
bB-2, a, (aA-2, b-1, a-(A-2), b-1)(B-1)/2, aA-1, c-(C-1^ .
We create a new hamiltonian cycle Y2 by replacing a subpath of the form [g] (a-(A-1), c, aA-1) with [g^aA-1, c, a-(A-1^. This is the same as the construction of Xq from X, but with a and a-1 interchanged, so the same calculation shows
(nY1)-1(nY2) is a conjugate of [c, a-(A-1)f-1 [c, a-(A-1)], which generates Zq.
Furthermore, since Y1 and Y2 both contain the oriented path [bB-3](b, a, b-1), and either the oriented edge [bB-2](a) or the oriented edge [bB-2a](a-1), Remark 3.2 provides hamiltonian cycles Y/ and Y2, such that (nY)-1 (nYj') generates Zp. Since all four hamiltonian cycles contain the oriented edge [c](c-1), Marusic's Method 2.11(2) applies. □
Case 5.9. Assume Zp^ C ([a, b]}, Zqv C ([a, c]}, and a centralizes G'/(G')pq.
Proof. We use Marusic's Method (2.11), so there is no harm in assuming S = {a, b, c}. Furthermore, Lemma 2.8 allows us to assume G' = Zpq, so ([a, b]} = Zp and ([a, c]} = Zq.
Note that [a, b-1 , c] £ Zp, [c, a 1,b] £ Zq, and [b, c 1, a] — e (because a centralizes G'). Since Zp n Zq = {e}, and the Three-Subgroup Lemma [7, Thm. 2.3, p. 19] tells us
[a, b-1, c]b[b, c-1, a]c[c, a-1, b]a = e,
D. Witte Morris: Odd-order Cayley graphs with commutator subgroup of order pq...	17
we conclude that [a, b-1, c] = [c, a-1, b] = e, so
c centralizes Zp and b centralizes Zq.
We know G' £ Z(G), because G is not nilpotent (see Assumption 5.1(4)). Since a centralizes G', this implies we may assume c does not centralize G' (by interchanging b and c if necessary). So c does not centralize Zq. Since a, b, and G' all centralize Zq, this implies c G (a, b, G'}. In other words, c G (a, b). Furthermore, applying Corollary 2.20 to the group (a, b) tells us that (a) = (a, b). Therefore (a) C (a, b) C (a,b,c), so Case 5.8 applies.	□
Case 5.10. Assume Zp^ C ([a, b]), Zqv C ([a, c]), and b, cG (a).
Proof. We use Marusic's Method (2.11), so there is no harm in assuming S = {a, b, c}. Furthermore, Lemma 2.8 allows us to assume G' = Zpq, so ([a, b]) = Zp and ([a, c]) = Zq. We may assume (a, b) = (a, c) = G, for otherwise Case 5.8 applies.
Let us begin by showing that a does not centralize any nontrivial element of G'. Suppose not. Then we may assume that a centralizes Zp. Let G = G/Zq = G/([a, c]). Since (a, c, G') = G, we know that (a, c, Zp) = G , so a is in the center of G. This contradicts the fact that ([a, b]) = Zp is nontrivial.
Since G is abelian (and because b, c G (a)), it is easy to choose a hamiltonian cycle (sj)d=1 in Cay(G/(a); S) that contains both an edge labeled b (or b-1) and an edge labeled c (or c-1). Note that
Co = ((si)d-11,a 1 a| -1, (s--2j+1, a-( 1 a| -2), s--M, a 1 a 1 -2)(=-1>/2, a)
is a hamiltonian cycle in Cay(G; S).
Subcase i. Assume |a| > 3. We may assume s1 = b-1 and s2 = c-1. Then C0 contains the four subpaths
(b-1), [b-1a2](a-1, b, a), [b-1](c-1), [b-1 c-1a-2](a, c, a-1).
Therefore, we may let g be either b-1 or b-1c-1 in Lemma 3.1, so Remark 3.2(2) tells us we have hamiltonian cycles Cb and Cc, such that (nC0)-1 (nCb) is a generator of Zp, and
(nC0)-1(nCc) is a generator of Zq. Since |a| > 3, we see that
Cb, like Co, contains [b-1]( c 1) and [b 1c 1a 2](a, c, a 1),
so Remark 3.2(2) provides a hamiltonian cycle CCb, such that (nCb)-1 (nC^) is a generator of Zq. Therefore, Marusic's Method 2.11(2) applies (since each of these four hamiltonian cycles contains the oriented edge [a-1](a)).
Subcase ii. Assume d > 3. We may assume s1 = b-1 and s3 = c-1. Then C0 contains the four subpaths
(b-1), [b-1a2](a-1, b, a), [s1s2](c-1), [s1s2c-1a2](a-1, c, a).
Therefore, we may let g be either b-1 or s1s2c-1 in Lemma 3.1, so Remark 3.2(2) tells us we have hamiltonian cycles Cb and Cc, such that (nC0)-1(nCb) is a generator of Zp, and (nC0)-1(nCc) is a generator of Zq. It is clear that Cb, like C0, contains [s1s2](c-1)
18
Ars Math. Contemp. 8 (2015) 149-162
and [sis2c-1a2](a-1, c, a), so Remark 3.2(2) provides a hamiltonian cycle C£, such that (nCb)-1(nC*) is a generator of Zq. Therefore, Marusic's Method 2.11(2) applies (since each of these four hamiltonian cycles contains the oriented edge [a-1](a)).
Subcase iii. Assume |a| = 3 and d = 3. Since d = 3, we may assume b = c (mod(a)) (by replacing c with its inverse if necessary). Let
Co = (b-1, c-1, a2, c, a-1, b, a2),
so C0 is a hamiltonian cycle in Cay(G; S). Then C0 contains the four subpaths
(b-1), [b-1a2](a-1, b, a), [b-1](c-1), [b-1c-1a-2](a, c, a-1).
Therefore, we may let g be either b-1 or b-1c-1 in Lemma 3.1, so Remark 3.2(2) tells us we have hamiltonian cycles
Cb = (a, b-1, a-1, c-1, a2, c, b, a)
and
Cc = (b-1, a-1, c-1, a2, c, b, a2),
such that (nC0)-1 (nCb) is a generator of Zp, and (nC0)-1(nCc) is a generator of Zq. Furthermore, Cc contains the oriented paths [ab-1](b) and [a-1](a, b-1, a-1), so, by letting g = a in Lemma 3.1 (and replacing b with b-1), Remark 3.2(2) tells us we have a hamiltonian cycle
Cbc = (a2, b-1 ,c-1, a2,c,a-1,b),
such that (nCc)-1(nCbc) is a generator of Zp. Therefore Marusic's Method 2.11(2) applies (since all four of these hamiltonian cycles contain the oriented edge [b-1 c-1](a)). □
Case 5.11. Assume Zp^ C ([a, b]), Zqv C ([a, c]), c G (a), andbG (a).
Proof. We use Marusic's Method (2.10), so there is no harm in assuming S = {a, b, c}. Furthermore, Lemma 2.8 allows us to assume G' = Zpq, so ([a, b]) = Zp and ([a, c]) = Zq. Also note that, from Assumption 5.1(5), we know c G {a±1}, so we must have |a| > 3.
Let d = |G/(a)|. Since c G (a), we have (a, b) = G, so (bd) is a hamiltonian cycle in Cay(G/(a); S). Choose r such that arbd G G' and 0 < r < |a| - 1. Assume r < |a|/2 (so r < |a| — 3), by replacing b with its inverse if necessary. Then letting k = |a| - 3 in Corollary 3.3 provides us with a hamiltonian cycle C0 = C|a|-3.
Choose I with c = a£, and write c = a£Y, where Zq C (7). We may assume 0 < I < |a|/2 (by replacing c with its inverse, if necessary). Then I < |a| — 3, so we see
from Figure 2 that C|a|_3 contains the path [a£b](a-(£+1)). Replacing this with the path
[a£b](c-1, a£-1, c-1) results in a hamiltonian cycle C1, such that (nC0)-1(nC1) is a conjugate of
c-1a£-1c-1 • a£+1 = (a^)-V-V7)-1 • a£+1 = 7-1(7-1)°.
Since |G| is odd, we know that a does not invert any nontrivial element of G', so this is a generator of (7), which contains ([a, c]) = Zq.
Furthermore, from Figure 2, we see that C|a|_3 contains both the oriented edge
[b-1a-1](b) and the oriented path [b-1a](a-1, b, a). Then, by construction, C1 also contains these paths. Therefore, we may apply Lemma 3.1 with g = b-1a-1, so Remark 3.2(1)
D. Witte Morris: Odd-order Cayley graphs with commutator subgroup of order pq...	19
tells us we have hamiltonian cycles G0 and G1, such that (nG®)-1(nG®) is a generator of Zp. Therefore Marusic's Method 2.11(2) applies (since there are many oriented edges, such as [a- 1](a-1), that are in all four hamiltonian cycles).	□
Case 5.12. Assume there do not exist a, b, c G S, such that ([a, b], [a, c]) = G'.
Proof. Let G = G/(G')pq, so G' = Zpq. The assumption of this case implies that we may partition S into two nonempty sets Sp and Sq, such that
•	Sp centralizes Sq in G, and
•	for r G {p, q}, and a, b G Sr, we have [a, b] G Zr.
Let Gp = (Sp), Gq = (Sq), and Z = Gp n Gq C Z(G).
Since G is notnilpotent (see Assumption 5.1(4)), we know that G' C Z(G). Therefore, we may assume Zq C Z(G) (by interchanging p and q if necessary). Since Gp n Gq C
Z(G), this implies Zq C Gp.
Subcase i. Assume there exist ap, bp, aq, bq G S, such that ([ap, bp]) = Zp, ([aq, bq]) = Zq, and {bp, bq} is a minimal generating set of (ap, bp, aq, bq)/(ap,aq). We use Marusic's Method (2.10) with S0 = {ap, bp, aq, bq}. Assume, for simplicity, that S = S0. Lemma 2.8 allows us to assume G' = Zpq, so G = G.
After perhaps replacing some generators with their inverses, it is easy to find:
•	a hamiltonian cycle (si)m=1 in Cay((ap, aq); ap,aq), such that sm-2 = ap and Sm-1 = aq, and
•	a hamiltonian cycle (tjj=1 in Cay(G/(ap, aq); bp, bq), such that t1 = bp and t3 =
bq.
We have the following hamiltonian cycle G0 in Cay(G; S):
n (it	< -1	\(m-1)/2 /	/,-1 im-1
C0 ^((si)i=1 , t2j-1, (s„-1-i)i-1 ,t2^j = 1 , (si)i=1 , (tm-j)j = 1 , s"J •
Much as in the proof of Lemma 3.1, we construct a hamiltonian cycle C1 by
•	replacing the oriented edge [sm1bp](b-1) with the path [sm1 bp](a-1, b-1, aq), and
•	the oriented path [sm1 a-1a-1](ap, bp, a-1) with [sm1a-1 a-1](bp).
Then there exist g, h G G, such that
(nG0)-1(nG1) = [b-1,aq]g [a-1 ,bp]h = eg • [a-1,bp]h = [a-1,bp]h,
which generates Zp.
Similarly, we may construct hamiltonian cycles G0 and C1 from G0 and C1 by
•	replacing the oriented edge [sm1t1t2bq](b-1) with the path [sm1t1 t2bq](a-1,b-1,
) , and
the oriented path [sm,1 a-1a-1t1t2](ap, bq, a-1) with [sm1a-1a-1t1t2](bq).
a
20
Ars Math. Contemp. 8 (2015) 149-162
Then, for k G {0,1}, essentially the same calculation shows there exist g', h' G G, such that
(ncfc)-1(nCk) =	[a-1 ,bq=	• eh =	,
which generates Zq.
All four hamiltonian cycles contain the oriented edge (s 1), so Marusic's Method 2.11(2) applies.
Subcase ii. Assume Gp is not the nonabelian group of order 27 and exponent 3. We will apply Marusic's Method (2.11), so Lemma 2.8 allows us to assume G' = Zpq, which means G = G.
Claim. We may assume Sq n (G'Z) = 0. Suppose aq G Sq n (G'Z). By the minimality of S, we know aq G Gp. Since Z and Zp are contained in Gp, this implies G' C (Gp, aq}. Therefore, the minimality of S implies that Sq \ {aq} is a minimal generating set of G/(Gp, aq}. So Subcase i applies. This completes the proof of the claim.
Now, applying Proposition 4.2 to Gq tells us there exist hamiltonian cycles Cq and Cq in Cay(Gq/Z; Sq), such that Cq and Cq have an oriented edge in common, and ((nCq)-1
(ncq)} = Zq.	_
Also, Theorem 4.1 provides hamiltonian cycles Cp and Cp in Cay(Gp; Sp), such that Cp and Cp have an oriented edge in common, and ((ncp)-1(ncp)} = Zp.
For r G {p, q}, write Cr = (srji)"= 1 and C = (ir-,»)^. Since Cr and C have an edge in common, we may assume sr,„r = tr,„r. Let
C = ((sP,i)j=Pl , (sq,i)n=q 1 ,
(sp,np-2i+1, (Si,n,-j)n==1, sp,np-2i, (sq,jj=2 )i=i >sq,n,) • (5.12A)
Then C is a hamiltonian cycle in Cay(G; S).
For r G {p, q}, a path of the form [g](sr,i )i=-1 appears near the start of C. We obtain a new hamiltonian cycle Cr in Cay(G; S) by replacing this with [gKir-,»)^-1. We can also construct a hamiltonian cycle Cp,q by making both replacements. Then
((nC )-1(nCr)} = ((nCr )-1(nC;)} = zr,
and
((nCq )-1 (nCp,q)} = ((nCp)-1(nCp)} = zp,
so Marusic's Method 2.11(2) applies (since all four hamiltonian cycles contain the oriented edge [s-n ](sq,n, )).
Subcase iii. Assume Gp is the nonabelian group of order 27 and exponent 3. We have p = 3, and Lemma 2.21(rTtells us ^ =1; i.e., G' = Z3 x Zqv. Therefore G = G/(G')q.
Let Cp = (sp,i)2=1 be a hamiltonian cycle in Cay(Gp; Sp). Also, for r = q, Theorem 4.1 provides hamiltonian cycles Cq = (sq,j)"= 1 and Cq = (tq,j)"= 1 in Cay(Gq; Sq),
such that sq,nq = tq,nq and (nCq)-1 (nCq) generates Zqv. Define the hamiltonian cycle C as in (5.12A) (with np = 27). We obtain a new hamiltonian cycle Cq in Cay(G; S) by
D. Witte Morris: Odd-order Cayley graphs with commutator subgroup of order pq...	21
e si s 2 S3
s 31-3
s 3£-1
Figure 5: A hamiltonian cycle C0.
replacing an occurrence of (s^)™!-1 with the path (iq,i)j= 11. Much as in Subcase ii, we have
((nC)-1(nCq)) = ((nC,)-1^)) = Zq,
so nC and nCq cannot both be trivial. Therefore, applying the Factor Group Lemma (2.7) with N = Zq provides a hamiltonian cycle in Cay(G; S), and then Lemma 2.8 tells us there is a hamiltonian cycle in Cay(G; S).	□
6 Proof of Case 5.5
In this section, we prove Case 5.5. Therefore, the following assumption is always in effect:
Assumption 6.1. Assume there exist a, b G S, such that ([a, b]) = G', |a| = |b| = 3, and (a) = (b).
The proof will consider two cases.
Case I. Assume #S > 2.
Proof. Let c be a third element of S, and let i = |G : (a, b)|. (Since S is a minimal generating set, and G' = ([a, b]) C (a, b), we must have i > 1.) We use Marusic's Method (2.10) with S0 = {a, b, c}; assume, for simplicity, that S = S0. Lemma 2.8 allows us to assume G' = Zpq. Let
(Sj)?= 1 = ((b,c,b-1,c)(^-1)/2,b2,c-(i-1),b),
so (sj)?! 1 is a hamiltonian cycle in Cay(G/(a); b, c). Note that
S1 = S5 = b.
sn„ —1
From the definition of (sj)?£ 1, it is easy to see that J}3! 1 s» = b° = e, so we have the following hamiltonian cycle C0 in Cay(G; a, b, c) (see Figure 5):
1
r< ii \3£-3 -1
Co = ((sj ).=1 , a , S3£—2, S3£—i, a , S3£,
i	—1 v3(£—1)/2	—1	\
(a, S2j—i,a , S2j jj=i , S3£—2, a , S3£—1,S3^.
Since s1 = b, we see that C0 contains the oriented edge (6), and it also contains the oriented path [a—2](a, 6, a—1), so Lemma 3.1 provides a hamiltonian cycle C1, such that
(nC0) —1(nC1) is a conjugate of [a, 6—1][a, b—1]a.
28
Ars Math. Contemp. 8 (2015) 149-162
Similarly, since s5 = b and s1s2s3s4 = c2, we see that G1 contains both the oriented edge [c2](b) and the oriented path [c2a-2](a, b, a-1), soLemma3.1 provides a hamiltonian cycle C2, such that
(nCi)-1(nC2) is also a conjugate of [a, b-1][a, b-1 ]a.
Since no element of G inverts any nontrivial element of G' (recall that |G| is odd), this implies that (nGj)-1(nGj) generates G' whenever i = j. So Marusic's Method 2.11(1) applies (since all three hamiltonian cycles contain the oriented edge [s1](s2).	□
Case II. Assume #S = 2.
Proof. We have S = {a, b}, so |G| = 9pMqv. We may assume p, q > 3, for otherwise Corollary 2.15 applies (perhaps after interchanging p and q).
One very special case with a lengthy proof will be covered separately:
Assumption 6.2. Assume Proposition 6.4 below does not provide a hamiltonian cycle in
Cay(G; S).
Under this assumption, we will always use the Factor Group Lemma (2.7) with N
•pq.
G', so Lemma 2.8 allows us to assume G' = Z
Let
C = (a-2,b-1,a,b-1,a-2 ,b2), so C is a hamiltonian cycle in Cay(G; a, b). We have
nC = a-2b-1ab-1a-2b2 = [a, b]>, b][a, b]6(a-3)fe2.	(6.2A)
Let G = G/Zp, so G' = Zq. Since > 3, we know gcd(|G|, |G'|) = 1, so G = G x G' [7, Thm. 6.2.1(i)]. Therefore G' n Z(G) is trivial, so we may
assume that a does not centralize Zq
(perhaps after interchanging a with b). Therefore a acts on Zq via a nontrivial cube root of unity. Since the nontrivial cube roots of unity are the roots of the polynomial x2 + x + 1, this implies that [a, b]a [a, b]a [a, b] = e, so
[a, b]a[a, b] = ([a,b]°2)-1 = ([a,b]°-1 )-1
(since |a| = 3). Furthermore, a-3 = e (since a has trivial centralizer in Zq). Hence,
nC = [a, b]a [a, b] [a, b]b(a-3)fe2 = ([a,b]°-1 )-1 [a, b]b e
([a, b]°- )-1 [a, b]b.
Therefore
nG = e unless yb = ya for all y G Zq.	(6.2B)
Hence, we may assume (nC) contains Zq (by replacing b with its inverse if necessary).
D. Witte Morris: Odd-order Cayley graphs with commutator subgroup of order pq...	68
Subcase i. Assume a centralizes Zp. Since G' n Z(G) is trivial, we know that b does not centralize Zp. Also, we may assume (nC) = G', for otherwise the Factor Group Lemma (2.7) applies. Therefore nC must project trivially to Zp. Fixing r, k e Z with
[a, b]b = [a, b]r and a-3 = [a,b]k
(and using the fact that r2 + r + 1 = 0 (modp)), we see from (6.2A) that this means
0 = 1 + 1 + r + kr2 = 1 - r2 + kr2 = r2(r - 1 + k) (modp),
so
k = 1 — r (mod p).
Therefore k = 0 (mod p) (since r is a primitive cube root of unity). Also, since a centralizes Zp, we have
[a-1, b-1]-kr = ([a, b-1]-1)-kr = (Mf- )-kr = [a, b]-k
= a3 = (a-1)-3 (modZq).
Therefore, replacing a and b with their inverses replaces k with -kr (modulo p), and it obviously replaces r with r2. Hence, we may assume that we also have
-kr = 1 - r2 = r3 - r2 = -(1 - r) r2 = -kr2 (mod p) ,
so r = 1 (modp). This contradicts the fact that b does not centralize Zp.
Subcase ii. Assume a does not centralize Zp. We may assume that the preceding subcase does not apply when a and b are interchanged (and perhaps p and q are also interchanged). Therefore, we may assume that either
•	b centralizes both Zp and Zq, in which case, interchanging p and q in (6.2B) tells us that nC projects nontrivially to both Zp and Zq, so the Factor Group Lemma (2.7) applies, or
•	b has trivial centralizer in G'.
Henceforth, we assume a and b both have trivial centralizer in G'.
We may assume yb = y° for y e Zq, by replacing b with its inverse if necessary. We may also assume (nC) = G' (for otherwise the Factor Group Lemma (2.7) applies). Since (nC) contains Zq, this means that (nC) does not contain Zp. By interchanging p and q in (6.2B), we conclude that xb = for x e Zp. We are now in the situation where a hamiltonian cycle in Cay(G; a, b) is provided by Proposition 6.4 below.	□
The remainder of this section proves Proposition 6.4, by applying the Factor Group Lemma (2.7) with N = Zqv. To this end, the following lemma provides a hamiltonian cycle in Cay (G/Zqv; S).
Lemma 6.3. Assume
•	G = Zp^ x (Z3 x Z3) = (x) x ((a) x (b0)), withp > 3,
•	b = xbo,
•	xb = xa 1 = xr, where r is a primitive cube root of unity in Zp^,
69
Ars Math. Contemp. 8 (2015) 149-162
•	k g Z, such that
o k = 1 (mod 3), o k = r (modpM), and o 0 < k < 3pM,
•	£ is the multiplicative inverse of k, modulo 3pM (and 0 < £ < 3pM),
•	C = (a, b-2, (a-1, b2)k-1, a-2, b2, (a, b-2)£-fc-1, a-2, (b-2, a)3^-1), and
•	(7 is the walk obtained from C by interchanging a and b, and also interchanging k and
Then either C or <7 is a hamiltonian cycle in Cay(G; a, b). Proof. Define
v2i+e = (ba)jbe	for e G {0,1},
Wj = (ba)j b-1,
and let V = {vj} and W = {wj}. Note that, since xab = x, we have |ab| = 3pM, so #V = 6pM and #W = 3pM, so G is the disjoint union of V and W. With this in mind, it is easy to see that C1 = (b-2, a)3pM is a hamiltonian cycle in Cay(G; a, b).
Removing the edges of the subpaths (b-2) and [(ba)k](b-2, a, b-2) from C1 results in two paths:
•	path P1 from b-2 = b to (ba)k, and
•	path P2 from (ba)fc+1b to e (since (ba)k(b-2ab-2) = (ba)k(bab) = (ba)fc+1b).
The union of P1 and P2 covers all the vertices of G except the interior vertices of the removed subpaths, namely,
all vertices except b-1, (ba)kb-1, (ba)kb, (ba)fc+1, and (ba)fc+1b-1.
By ignoring y in calculation (6.4A) below, we see that b-1a-1 = (a-1b-1)k, which means
ab = (ba)k.
Since b-2 = b, this implies
ab-2 = (ba)k.
Also, since a-1 = a2, we have
ba-1b2 = ba2b2 = (ba)(ab)b = (ba)((ba)k)b = (ba)fc+1b.
Therefore
Q1 = (a, b-2) is a path from the end of P2 to the end of P1,
and
Q2 = [b](a-1, b2) is a path from the start of P1 to the start of P2. So, letting -P1 be the reverse of the walk P1, we see that
C2 = Q1 U -P1 U Q2 U P2
D. Witte Morris: Odd-order Cayley graphs with commutator subgroup of order pq...	70
is a closed walk.
Note that the interior vertices of Q1 are
a = (ab)b-1 = (ba)kb-1
and
ab-1 = (ab)b = (ba)k b, and the interior vertices of Q2 are
ba-1 = ba2 = (ba)(ab)b-1 = (ba)(ba)kb-1 = (ba)k+1b-1 and ( )
ba-1b = ((ba)k+1b-1)b = (ba)k+1. These are all but one of the vertices that are not in the union of P1 and P2, so
C2 is a cycle that covers every vertex except b-1.
Notice that the only a-edge removed from C1 is [(ba)kb-2](a) = [(ba)kb](a). Since
k2 = (r2)2 = r4 = r ^ 1 (modp^),
and I is the multiplicative inverse of k, modulo 3pM, we know k = I, so this removed edge is not equal to [(ba)eb](a). Therefore [(ba)eb](a) is an edge of C2. Now, we create
a walk C* by removing this edge from C2, and replacing it with the path [(ba)eb](a-2). Since ( )
(ab)e = ((ba)k )e = (ba)ke = ba, we see that the interior vertex of this path is
[(ba)eb]a-1 = [b(ab)e]a-1 = [b(ba)]a-1 = b2 = b-1.
Therefore C* covers every vertex, so it is a hamiltonian cycle.
Since ab = (ba)k and ba = (ab)e, it is obvious that interchanging a and b will also interchange k and I. Therefore, we may assume k < I, by interchanging a and b if necessary. Then the edge [(ba)eb](a) is in P2, rather than being in P1. If we let P2' be the path obtained by removing this edge from P2, and replacing it with [(ba)eb](a-2), then we have
C = ( (a, b-2), (a-1, b2)k-1, a-1, (a-1,b2), (a, b-2)e-k-1, a-2, (b-2, a)3PM-e-1 ) = Q1 U -P1 U Q2 U P2
= C *
is a hamiltonian cycle in Cay(G; a, b).	□
Proposition 6.4. Assume
•	G = Z3 x Z3,
•	G' = x Zqv, with p = q and p, q > 3,
•	S = {a, b} has only two elements,
•	a and b have trivial centralizer in G', and
71
Ars Math. Contemp. 8 (2015) 149-162
ab centralizes Zp/J. and ab 1 centralizes Zqv.
Then Cay (G; a, b) has a hamiltonian cycle. Proof. Since gcd(|G|, |G'|) = 1, we have
G = G' x G = (ZPM x Zqv) x (Z3 x Z3).
Write Zpm = (x) and Zqv = (y). Since a does not centralize any nontrivial element of G', we may assume a G Z3 x Z3 (after replacing it by a conjugate). Write b = Yb0, with
Y	G G' and b0 G Z3 x Z3. Since (a, b) = G, we must have (y) = G', so we may assume
Y	= xy; therefore b = xyb0.
Choose r G Z with x" 1 = xr. Since |a| = 3 and a does not centralize any nontrivial element of Zp^, we know that r is a primitive cube root of unity, modulo pM. Also, since ab centralizes Zp^, we have xb = xr.
Define k and I as in Lemma 6.3. Then, letting G = G/Zqv (and perhaps interchanging a with b), Lemma 6.3 tells us that
C = (a, b-2, (a-1, b2)k-1, a-2, b2, (a, b-2)£-fc-1, a-2, (b-2, a)3^-£-1)
is a hamiltonian cycle in Cay (G; a, b).
To calculate the voltage of C, choose s G Z with ya = ys, and let
y1 = ysM1^-^-1) = ys2-1
(since 1 + s + s2 = 0 (mod q) and k = 1 (mod 3)), and note that
(a-1b-1)k = (a-1(xyb0)-1)	(6.4A)
( -U-1 -1 -1)fc = a b0 y x
= x-k (a-1b-1y-1)k	(x commutes with a-1b-1 and y)
x-r (a-1b0-1)ky-(1+s+s2+( r (rnobdpM) and ) y 0 ) y	Vya 60 = ya 60 = ys = yv
= x r b- a y s y1
a and b0 commute, k 1 y (mod 3), and definition of y1
b-1x-1y-1a-1y1	(xr = xbo and ys' = ya' = ya 1)
b 1a 1ys" 1	(b = xybo and y1 = ys" 1).
D. Witte Morris: Odd-order Cayley graphs with commutator subgroup of order pq...	72
Therefore
nC = ab-2(a-1b2)k-1a-2b2(ab-2)£-k-1a-2(b-2a)3^-£-1
= ab(a-1b-1)k-1ab(b(ab)£-k-1a) (ba)3^-£-1 = ab(a-1b-1)k (a-1b-1)-1ab(ba)£-k (ba)-£-1 = ab(a-1b-1)k (ba)ab(ba)-k(ba)-1
= ab(b-1a-1 ys2-1)ba2b(b-1a-1ys2-1) (a-1b-1)
= ys"-1bays -1a-1b-1
= y yv
y
(s2-1)(1+s)
(|a| = |b| =3) (|ba| = 3pM)
(ba)-k = (a-1b-1)k = b-1a-1ys2-1
,a-16-
22 ..a b
ys = ys
Since s is a primitive cube root of unity modulo qv, we know s ^ ±1 (mod q). Therefore, the exponent of y is not divisible by q, which means nC ^ (yq}, so nC generates Zqv. Hence, the Factor Group Lemma (2.7) provides the desired hamiltonian cycle in
Cay(G; a,b).	□
References
[1]	B.Alspach, Lifting Hamilton cycles of quotient graphs, Discrete Math. 78 (1989), 25-36. MR 1020643
[2]	S.J. Curran and J. A. Gallian, Hamiltonian cycles and paths in Cayley graphs and digraphs—a survey, Discrete Math. 156 (1996), 1-18. MR 1405010
[3]	E. Durnberger, Connected Cayley graphs of semidirect products of cyclic groups of prime order by abelian groups are Hamiltonian, Discrete Math. 46 (1983), 55-68. MR 0708162
[4]	E. Durnberger, Every connected Cayley graph of a group with prime order commutator group has a Hamilton cycle, in: B.Alspach, C. Godsil (eds.), Cycles in Graphs (Burnaby, B.C., 1982), North-Holland, Amsterdam, 1985, 75-80. MR 0821506
[5]	E.Ghaderpour and D.W.Morris, Cayley graphs of order 27p are hamiltonian, Internat. J. Comb. 2011 (2011), Article ID 206930, 16 pages. MR 2822405
[6]	E. Ghaderpour and D. W. Morris, Cayley graphs on nilpotent groups with cyclic commutator subgroup are hamiltonian, Ars Contemp. Math. 7 (2014), 55-72. MR 3029452
[7]	D. Gorenstein, Finite Groups, Chelsea, New York, 1980. MR 0569209
[8]	M. J. Hall, The Theory of Groups, Macmillan, New York, 1959. MR 0103215
[9]	B. Huppert, Endliche Gruppen I, Springer, Berlin, 1967. MR 0224703
[10]	K.Keating and D.Witte, On Hamilton cycles in Cayley graphs with cyclic commutator subgroup, in: B.R. Alspach, C.D.Godsil (eds.), Cycles in Graphs (Burnaby, B.C., 1982), North-Holland, Amsterdam, 1985, 89-102. MR 0821508
[11]	K.Kutnar, D.Marusic, J.Morris, D.W.Morris, and P.Sparl, Hamiltonian cycles in Cayley graphs whose order has few prime factors, Ars Math. Contemp. 5 (2012), 27-71. MR 2853700
[12]	D.Marusic, Hamiltonian circuits in Cayley graphs, Discrete Math. 46 (1983), 49-54. MR 0708161
73	Ars Math. Contemp. 8 (2015) 149-162
[13]	I. Pak and R. RadoiciC, Hamiltonian paths in Cayley graphs, Discrete Math. 309 (2009), 55015508. MR 2548568
[14]	D.Witte, Cayley digraphs of prime-power order are Hamiltonian, J. Combin. Theory Ser. B 40 (1986), 107-112. MR 0830597
[15]	D. Witte and J. A. Gallian, A survey: Hamiltonian cycles in Cayley graphs, Discrete Math. 51 (1984), 293-304. MR 0762322