/^creative ^commor
ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 7 (2014) 55-72
Cayley graphs on nilpotent groups with cyclic commutator subgroup are hamiltonian
Ebrahim Ghaderpour, Dave Witte Morris
Department of Mathematics and Computer Science, University of Lethbridge Lethbridge, Alberta, T1K3M4, Canada
Received 27 November 2011, accepted 2 July 2012, published online 22 February 2013
Abstract
We show that if G is any nilpotent, finite group, and the commutator subgroup of G is cyclic, then every connected Cayley graph on G has a hamiltonian cycle.
Keywords: Cayley graph, hamiltonian cycle, nilpotent group, commutator subgroup. Math. Subj. Class.: 05C25, 05C45
1 Introduction
It has been conjectured that every connected Cayley graph has a hamiltonian cycle. See [4, 10, 11, 14, 15, 17] for references to some of the numerous results on this problem that have been proved in the past forty years, including the following theorem that is the culmination of papers by Marusic [12], Durnberger [5, 6], and Keating-Witte [9]:
Theorem 1.1 (D.Marusic, E.Durnberger, K.Keating, and D. Witte, 1985). Let G be a nontrivial, finite group. If the commutator subgroup [G, G] of G is cyclic of prime-power order, then every connected Cayley graph on G has a hamiltonian cycle.
It is natural to try to prove a generalization that only assumes the commutator subgroup is cyclic, without making any restriction on its order, but that seems to be an extremely difficult problem: at present, it is not even known whether all connected Cayley graphs on dihedral groups have hamiltonian cycles. (See [1, 2] and [15, Cor. 5.2] for the main results that have been proved for dihedral groups.) In this paper, we replace the assumption on the order of [G, G] with the rather strong assumption that G is nilpotent:
Theorem 1.2. Let G be a nontrivial, finite group. If G is nilpotent, and the commutator subgroup of G is cyclic, then every connected Cayley graph on G has a hamiltonian cycle.
E-mail addresses: Ebrahim.Ghaderpoor@uleth.ca (Ebrahim Ghaderpour), Dave.Morris@uleth.ca, http://people.uleth.ca/~dave.morris/ (Dave Witte Morris)
©® This work is licensed under http://creativecommons.Org/licenses/by/3.0/
56
Ars Math. Contemp. 7 (2014) 41-54
The proof of this theorem is based on a variant of the method of D.Marusic [12] that established theorem 1.1 (cf. [9, Lem. 3.1]).
Remark 1.3. Here are some previous results on the hamiltonicity of the Cayley graph Cay(G; S) when G is nilpotent:
1.	Assume G is nilpotent, the commutator subgroup of G is cyclic, and S has only two elements. Then a hamiltonian cycle in Cay(G; S) was found in [9, §6] (see proposition 3.16). The present paper generalizes this by eliminating the restriction on the cardinality of the generating set S.
2.	For Cayley graphs on nilpotent groups (without any assumption on the commutator subgroup) it was recently shown that if the valence is at most 4, then there is a hamiltonian path (see [13]).
3.	Every nilpotent group is a direct product of p-groups. For p-groups, it is known that every Cayley graph has a hamiltonian cycle ([16], see theorem 3.13). Unfortunately, we do not know how to extend this to direct products.
4.	Every abelian group is nilpotent. It is well known (and easy to prove) that Cayley graphs on abelian groups always have hamiltonian cycles. In fact, there is usually a hamiltonian path from any vertex to any other vertex (see [3]).
Acknowledgments. We thank Dragan Marusic and Mohammad Reza Salarian for their comments that encouraged this line of research. We also thank an anonymous referee for reading an earlier version of the paper very carefully, and providing many corrections and helpful comments.
2 Assumptions and notation
We begin with some standard notation:
Notation 2.1. Let G be a group, and let S be a subset of G.
•	Cay(G; S) denotes the Cayley graph of G with respect to S. Its vertices are the elements of G, and there is an edge joining g to gs for every g G G and s G S.
•	G' = [G, G] denotes the commutator subgroup of G.
•	Sr = { sr | s G S } for any r G Z. (Similarly, Gr = { gr | g G G }.)
•	S±x = S U S-1.
•	#S is the cardinality of S.
Note that if S happens to be a cyclic subgroup of G, then Sr is a subgroup of S.
We now fix notation designed specifically for our proof of theorem 1.2: Notation 2.2.
•	G is a nilpotent, finite group,
•	N is a cyclic, normal subgroup of G that contains G',
•	g ^ g is the natural homomorphism from G to G/N = G,
•	S = {<t1; ct2, • • •, is a subset of G, such that
E. Ghaderpour and D. W. Morris: Cayley graphs on nilpotent groups with...
57
o S is a minimal generating set for G, and
o i = #S = #S > 2,
The minimality of S implies that e G S, and that if s G S and |s| > 3, then s-1 G S.
Sk = { oi | i < k } for 1 < k < i, Gk = (Sfc>N, and
•	mfc = |Gfc : Gfc_i|. Definition 2.3.
•	If (si)"=1 is a sequence of elements of S±1 and g G G, we use g(si)"=1 to denote the walk in Cay(G; S) that visits (in order) the vertices
g,gS1, gS1S2, .. .,, gS1S2 • • • s„.
•	If C = g(si)"=1 is any oriented cycle in Cay(G; S), its voltage is f]"=1 si. This is an element of N, and it may be denoted nC.
•	For S0 C S, we say the walk g(si)"=1 covers S^1 if it contains an oriented edge labeled s and a (different) oriented edge labeled s-1, for every s g S0. (That is, there exist i, j with i = j, such that si = s and sj = s-1. When |s| = 2, this means
si sj s.)
•	Vk is the set of voltages of oriented hamiltonian cycles in the graph Cay(Gk; Sk) that cover S^1.
Notation 2.4. For k g Z+, we use (s1;..., sn)k to denote the concatenation of k copies of the sequence (s1;..., sn). Abusing notation, we often write sk and s_k for
(s)k = (s, s,..., s) and (s-1)k = (s-1, s-1,..., s-1),
respectively. Furthermore, we often write ((s1;..., sm), (t1;... ,tn)) to denote the concatenation (s1;..., sm, i1;..., tn). For example, we have
((a3, b)2, c-2)2 = (a, a, a, b, a, a, a, b, c-1, c-1, a, a, a, 6, a, a, a, 6, c-1, c-1).
The following well-known, elementary observation is the foundation of our proof:
Lemma 2.5 ("Factor Group Lemma" [17, §2.2]). Suppose
•	N is a cyclic, normal subgroup of G,
•	C = g(si)"=1 is a hamiltonian cycle in Cay(G; S), and
•	the voltage nC generates N.
Then (s1,..., sn)|N 1 is a hamiltonian cycle in Cay(G; S).
With this in mind, we let N = G', and we would like to find a hamiltonian cycle in Cay(G; S) whose voltage generates N. In almost all cases, we will do this by induction on
58
Ars Math. Contemp. 7 (2014) 41-54
I = #S, after substantially strengthening the induction hypothesis. Namely, we consider the following assertion (a') for 2 < k < I and e G {1,2}:
there exists hk G N, such that, for every x G N,
(Vk n hk (G'k)e)x contains a generator of	(a')
a subgroup of N that contains (G'k)e.
For e = 2, we also consider the following slightly stronger condition, which we call : a' holds, and (hk, (G'k)2} contains G'k.	(a'+)
Lemma 2.6. Let N = G'. If either aj or «2+ holds, then there is a hamiltonian cycle in Cay(G; S) whose voltage generates N.
Proof. Note that G' = G' = N. Since V' consists of voltages of hamiltonian cycles in Cay(G; S), it suffices to find an element of V' that generates G'.
If we assume aj, then the desired conclusion is immediate, by taking x = e in that assertion.
Similarly, if we assume a2+, then taking x = e in a2 tells us that some element 7 of
V' n h'(G')2 generates a subgroup of N that contains (G')2. Then, since 7 G (G')2h', and (h', (G')2} contains G', we have
N D (7} = (7, (G')2} = (h', (G')2} D G' = N.	□
Remark 2.7.
1.	If |G'k | is odd, then (G'k)2 = G'k, so we have a' ^ a' ^ a'+ in this case. Thus, the parameter e is only of interest when |G'| is even.
2.	It is not difficult to see that a' ^ a'+, but we do not need this fact. Our proof of aj or a2+ is by induction on k. Here is the outline:
I.	We prove a base case of the induction: a2 is usually true (see proposition 4.1).
II.	We prove an induction step: under certain conditions, a' ^ a'+1 and a'+ ^ a'+x (see proposition 5.4).
III. We prove aj or a2+ is usually true, by bridging the gap between a2 and either a3 or a|+, and then applying the induction step (see corollary 6.1 and proposition 6.2).
3 Preliminaries
3A Remarks on voltage
Remark 3.1. By definition, it is clear that all translates of an oriented cycle C in Cay(G; S) have the same voltage. That is,
n(g(si)n=i) = n((si)n=i).
Remark 3.2. If | N| is square-free (which is usually the case in this paper), then N is contained in the center of G (because N is the direct product of normal subgroups of prime order, and it is well known that those are all in the center [8, Thm. 4.3.4]). In this situation,
E. Ghaderpour and D. W. Morris: Cayley graphs on nilpotent groups with...
59
the voltage of a cycle in Cay(G; S) is independent of the starting point that is chosen for its representation. That is, if (tj)™= i is a cyclic rotation of (sj)n=i, so there is some r G {0,1, 2,..., n} with ti = si+r for all i (where subscripts are read modulo n), then
n(ij)n=i = sr+1 sr+2 • • • sn si«2 • • • «r = («1 • • • «r )"^n(si)n=J si • • • sr = n(sj)n=i, because n(si)n=i g N c Z(G).
The following observation is useful for calculating voltages: Lemma 3.3. If a, b G G, G' c Z(G), and pi; qi;... ,pr, qr G Z, then
aPl bqi ap2 bq2 •• • apr bqr = api+-+pr bqi+ [a,b]-s, where £ = piqj.
Proof. The desired conclusion is easily proved by induction on r, using the fact that, since
G' c Z(G), we have [ap, bq] = [a, b]pq for p, q G Z [7, Lem. 2.2(i)].	□
3B Facts from group theory
Lemma 3.4. If |G'fc| is square-free, then |G'fc/G'fc_i| is a divisor of both |Gk_i| and
|Gfc/Gfc_i|.
Proof. We may assume k = so G = Gk. Let p be a prime factor of |G'/G'fc_i|, let P be the Sylow p-subgroup of G, and let ^: G ^ P be the natural projection. Since |G'| is square-free, it suffices to show that | Gk _ i | and | Gk /Gk _ i | are divisible by p.
We may assume |G'| = p and G'fc_i = {e}, by modding out the unique subgroup of index p in G'. Therefore ^(Gfc_i) is abelian, so it is a proper subgroup of P. Since G' = P' c $(P), this implies ^(Gfc_i)G' is a proper subgroup of P, so its index is divisible by p. Hence |G/Gk_i | is divisible by p.
There must be some t g Sk_i, such that [fffc,t] is nontrivial. Hence <^(t) G Z(G) D G', so p is a divisor of |<^(t)|, which is a divisor of |Gk_i |.	□
The following fact is well known and elementary, but we do not know of a reference in the literature. It relies on our assumption that G' is cyclic.
Lemma 3.5. We have ([s, t] | s, t G S) = G' if N c Z(G).
Proof. Let H = ([s, t] | s,t G S). Then H is a normal subgroup of G, because every subgroup of a cyclic, normal subgroup is normal. In G/H, every element of S commutes with all of the other elements of S (and with all of N), so G/H is abelian. Hence G' c H.	□
3C Elementary facts about cyclic groups of square-free order
Lemma 3.6. Assume |N | is square-free, and H and K are two subgroups of N. Then:
1.	There is a unique subgroup KL of N, such that N = K x K
2.	KL is a normal subgroup of G.
3.	K C H iff H = N in G = G/K^.
60
Ars Math. Contemp. 7 (2014) 41-54
Proof. (1) Since N is cyclic, it has a unique subgroup of any order dividing |N|; let KL be the subgroup of order |N/K |. Since |N | is square-free, we have gcd( |K |, |K = 1, so N = K x K
(2)	It is well known that every subgroup of a cyclic, normal subgroup is normal (because no other subgroup of N has the same order).
(3)	We prove only the nontrivial direction. Since H = N, we know that |K| = |N| is a divisor of |H|. So |H| has a subgroup whose order is |K|. Since K is the only subgroup of N with this order, we must have K C H.	□
Remark 3.7. When we want to show that some subgroup H of N contains some other subgroup K, Lemma 3.6 often allows us to assume K = N (by modding out Kwhich means we wish to prove H = N.
Lemma 3.8. Suppose
•	y is a generator of N,
•	x G N, and
•	a > max(|N|, 5).
Then, for some i with 1 < i < [(a — 1)/2J, we have N2 C (y-2®x).
Proof. Write x = Yh, where 1 < h < |N|, choose r G {1, 2} such that h — r is even, and let
. \ r if h G {1,2}, i = j(h — r)/2 if h> 2.
Then h — 2i G {±r} c {±1, ±2}, so N2 C (Yh-2i) = (y-2®x).	□
Lemma 3.9. If
•	N is a cyclic group of square-free order,
•	m > |N|,
•	k > 2,
•	T = {yi, ..., Yk} generates N,
•	h G N, and
•	Cay(N; T) is not bipartite,
then we may choose a sequence (j®)™-1 of elements of {1,2,..., k}, and y® G {y±X} for each i, such that y®+1 = Yi whenever ji+1 = j®, and
(hYiYa ••• Y^-i) = N.	(3.10)
Proof. Let us assume |N | > 3. (The smaller cases are very easy to address individually.)
We begin by finding Yi, Y®,..., Ym-1 G T±1, such that (hY®Y2 ''' Ym-1) contains N2 (or N, if appropriate), but without worrying about the requirement that y2+1 = Yi whenever ji+1 = ji.
Let y be a generator of N, and assume h-1Y = e (by replacing y with its inverse, if necessary). Since Cay(N; T) is not bipartite, there is a walk (Yii)l=1 from e to h-1Y, such
that r = m — 1 (mod 2).
E. Ghaderpour and D. W. Morris: Cayley graphs on nilpotent groups with...
61
We now show the walk can be chosen to satisfy the additional constraint that r < |N | (so r < m - 1). We know that Cay(N; T) has a hamiltonian cycle C (since N is abelian). Since Cay(N; T) is not bipartite, C must have a chord L of even length. We may assume one endpoint of L is e, since Cay(N; T) is vertex transitive. Let z be the other endpoint of L. Being a hamiltonian cycle, C can be written as the union of two edge-disjoint paths from e to h-1Y. Let P be the one of these paths that contains a subpath of even length from e to z, and let P be obtained from P by replacing this subpath with the edge L. Then P and P are two paths from e to h-1Y. Both have length less than |N |, and their lengths are of opposite parity. Now
hYi7a • • • Y* (YiY-1)(m-1-r)/2 = Y generates N,
as desired.
To complete the proof of the lemma, we modify the above sequence y |, y| , ..., y^-i to satisfy the condition that y|+1 = YÎ whenever ji+ 1 = ji. First of all, since N is commutative, we may collect like terms, and thereby write
4= 4=	4=	mi m2	mk -ni —no	-nk
Y 1Y2 ••• Ym- 1 = Yi 1Y2 2 ••• Yfc kYi 1Y2 2 ••• Yfc k
where m1 + ••• + mk + n1 + ••• + nk = m -1. Notice that if mk and n1 are both nonzero, then no occurrence of Yi is immediately followed by y- 1 ; so we have y|+1 = Yi whenever ji+1 = j^, as desired. Therefore, by permuting y1, ..., Yfc, we may assume mi = ni = 0 for all i > 1. Also, we may assume m1 and n1 are both nonzero, for otherwise we have
Yi = Yi for all i and j. Then, since Y1Y-1 = Y2Y-1, we have
4= 4=	4=	mi -ni
Y1Y2 ••• Ym— 1 = Yi 1 Yi 1
m-i— 1 — (ni — 1) -1
: Y1 1 Y2Y1 y2 •
We can assume n > m1 (by replacing 71 with its inverse, if necessary). Then
>	m — 1	>	riN 1 —11
	2		2
> 2,
so this new representation of the same product satisfies the condition that Yi is never immediately followed by y—1 . This completes the proof.	□
Corollary 3.11. Assume |N| is square-free and k > 2 (and e G {1, 2}, as usual). For convenience, let m = mk+1 and a = <rk+1. If h G N, then there exists a sequence
(si)m=11 of elements of Sk, and s2
Si+1 = si, and
G jsf1} for each i, such that s
i+1
whenever
1
h [a, s2], (G'k)j contains
G
k+1
if there exist s, s' G Sk, such that
| [a, s] | is even and | [a, s'] | is odd,
i=1
(G'fc+ir if |G'fc+i/G'fc | is odd, .(G'k+1)2 otherwise. Proof. For each s G Sk, let ys = [a, s]. Also, let
(3.12)
T = { Ys | s G Sk }Ç Gk+1 Ç N•
=s
62
Ars Math. Contemp. 7 (2014) 41-54
Let
1	if there exist t, t' G T, such that |t| is even and |t'| is odd, e if |G'fc+1/G'fc| is odd,
2	otherwise.
Lemma 3.6 allows us to assume (G'fc+1)e = N, by modding out ((G'fc+1)e)±. We can also assume (G'k ) is trivial, by modding it out. We claim that (T) = N. We have
(T, G') D ({ [afc+i,s] | s G Sk },{ [s,t] | s,t G Sk }) = ({ [s,t] | s,t G Sk+i })
= G'k+1	(see Lemma 3.5)
= N.
Since (G'fc)e is trivial, this implies |N : (T}| < e. Thus, if the claim is not true, must have |N : (T}| = e = 2. In particular, |N| is even. Since (G'fc+1)? = N, we conclude that e = 1, so the definition of e (together with the fact that e = 2) implies that T contains an element of even order. So |(T}| is even, which contradicts the fact that |N : (T}| = 2 is even (and | N| is square-free). This completes the proof of the claim.
We also claim that Cay(N; T) is not bipartite. We may assume |N| is even (for otherwise the claim is obvious). Since (G'fc+1) = N, this implies ? = 1. However, the claim is also obviously true if there exist t,t' G T, such that |t| is even and |t'| is odd. Hence, we may assume |G'fc+1/G'fc| is odd, and e = ? = 1. Since (G'fc)e is trivial, this implies |G'fc | is odd, which contradicts the fact that | N| is even. This completes the proof of the claim.
The desired conclusion is now immediate from Lemma 3.9 (since ys = [a, s] and (Ys)-1 = [a, s-1]).	□
3D Results from [9] and [16]
The following result from [16] allows us to assume G is not a 3-group. (Since we always assume that G' is cyclic, a short proof of the special case we need can be found in [15, Thm. 6.1].)
Theorem 3.13 (Witte [16]). If |G| is apower of some primep, then every connected Cayley graph on G has a hamiltonian cycle.
The following simple observation usually allows us to assume |N| is square-free.
Lemma 3.14 ([9, Lem. 3.2]). Let G = G/$(N), where $(N) is the Frattini subgroup of N [8, §10.4]. Then:
1.	|N| is square-free, and
2.	if there is a hamiltonian cycle in Cay(G/N; S) whose voltage generates N, then there is a hamiltonian cycle in Cay(G/N; S) whose voltage generates N.
Lemma 3.15 (Keating-Witte [9, Case 6.1]). If |G2| is even, then Cay(G2; S2) has a hamiltonian cycle whose voltage is a generator of G2.
E. Ghaderpour and D. W. Morris: Cayley graphs on nilpotent groups with...
63
Proof. For the reader's convenience, we provide a proof. We may assume |<ri | is even (by interchanging a1 and a2 if necessary). For convenience, let n = |aT| and m = m2. Then
/ m —1 /	-(m-2)	m-2^(n-2)/2	-(m-1) -(n-1)\
(a2 , (a1,a2 ,a1,a2 ) ,a1,a2 ,a1 J
is a hamiltonian cycle in Cay(G2; S2).
Lemma 3.14 allows us to assume |G2| is square-free, which implies G2 is in the center of G2 (see remark 3.2). Also, from Lemma 3.4, we know that | [a1; a2] | is a divisor of both m and n. Therefore
(a1a2-(m-2)a1a2m-2)(n-2)/2 = (a2 K am-2])(n-2)/2
= an-2 [a1,a2](m-2)(n-2)/2 = a^2 [a^]2
and
[a-(m-1), a-(n-1)] = Ka1](m-1)(n-1) = [a2,a] = [a^]-1, so the voltage of this cycle is
m-1 ( -(m-2) m-2)(n-2)/2 -(m-1) -(n-1) a2 a1 a2 a1 a2 a1 a2 a1
m-1/ n-2 r	„.-(m-1) -(n-1)
= a2 la1 [a1,a2] Ja1a2 a1
m-1 n-1 -(m-1) -(n-1) r	i2
= a2 a1 a2 a1 [a1,a2]
r -(m-1) -(n-1)n r	-|2
= [a2 ,a1 ][a1,a2]
= [a1,a2],
which generates G2 (see Lemma 3.5).	□
The following result allows us to assume t > 3.
Proposition 3.16 (Keating-Witte [9, §6]). If t = 2 and N = G', then Cay(G; S) has a hamiltonian cycle.
Proof. For the reader's convenience, we provide a proof (using the main result of Section 4 below). We may assume |G/G'| is odd, for otherwise a hamiltonian cycle is obtained by combining Lemma 3.15 with the Factor Group Lemma (2.5). We may also assume that |G| is not a power of 3, for otherwise theorem 3.13 applies. This implies it is not the case that |s| = 3 for every s G S.
If |G'| is square-free, then proposition 4.1 tells us that «2 is true. Also, since |G/G'| is odd, we know |G'| is odd (cf. Lemma 3.4), so a^ implies that «2 is true (see remark 2.7(1)). Therefore, the Factor Group Lemma (2.5) provides a hamiltonian cycle in Cay(G; S) (see Lemma 2.6). Then Lemma 3.14 tells us there is a hamiltonian cycle even without the assumption that |G'| is square-free.	□
4 Base case of the inductive construction
Recall that the condition is defined in Section 2.
Proposition 4.1 (cf. [9, Case 6.2]). Assume |N| is square-free (and t > 2). Then «2 is true unless |G2| = m2 = |OT| = |02| = 3.
64
Ars Math. Contemp. 7 (2014) 41-54
Proof. For convenience, let
a = <7i, b = <72, and m = m2,
and define r by
b™ = ar and 0 < r < |a|. We may assume:
•	I = 2, so S = S2 = {a, b} and G = G2.
•	(G')2 is nontrivial. (Otherwise, the condition about generating (G')2 is automatically true, so it suffices to show V2 = 0, which is easy.)
•	Either |a| is even, or m is odd (by interchanging <1 and <2 if necessary).
•	|a| = 3 (by interchanging <1 and <2 if necessary: if |71| = |<2| = 3, then m = 3 and, from Lemma 3.4, we also have |G' | =3, which means we are in a case in which the statement of the proposition does not make any claim).
•	r > |a|/2 (by replacing a with its inverse if necessary).
Note that |G'| is a divisor of both |a| and m (see Lemma 3.4). Since (G')2 is nontrivial, this implies that |a| and m both have at least one odd prime divisor.
Case 1. Assume m = 3. Since |G'| is a divisor of m, we must have |G'| = 3, so |a| must be divisible by 3. Then, since |a| = 3, we must have |a| > 6. Furthermore, by applying Lemma 3.4 with a and b interchanged, we see that |G/(b}| is also divisible by |G'| = 3, which means that r is divisible by 3.
We claim that it suffices to find two elements y^Y2 g V2, such that y1 = y2 and Y1 G y2G'. To see this, note that, for any x g N, there is some i G {1,2}, such that (y»x} has nontrivial projection to G' (with respect to the unique direct-product decomposition N = G' x (G')^). Since |G'| is prime, this implies that the projection is all of G', so Lemma 3.6 tells us that (y»x} contains G'. This establishes a1, which is equivalent to «2 (see remark 2.7(1)). This completes the proof of the claim.
Assume, for the moment, that r = 3. Then, since r > |a|/2 and |a| > 6, we must have |a| = 6. Here are two hamiltonian cycles in Cay(G; a, b) that cover S±1:
(b-1, a-2, b-4, a-2, b-1, a3, b2, a, b-2)
and
(b-1, a-2, b-1, a, b-1, a-1, b-2, a-1, b-1, a2, b2, a, b-2) (see Figure 1). By using Lemma 3.3, we see that their voltages are
b-1a-2b-4a-2b-1a3b2ab-2 = b-6[a, b]-(-10) = b-6[a, b]
and
b-1a-2b-1ab-1a-1b-2a-1b-1a2b2ab-2 = b-6[a, b]-(-8) = b-6[a,b]2,
respectively. So we may let y1 = b-6 [a, b] and y2 = b-6 [a, b]2. We may now assume r > 6 (since r is divisible by 3). Let
j. = |{0,1} if r = |a|,
{1, 2} if r
=a
E. Ghaderpour and D. W. Morris: Cayley graphs on nilpotent groups with...	65
Figure 1: Two hamiltonian cycles in Cay(G; {a, 6}) when m = r = 3.
Figure 2: A hamiltonian cycle in Cay(G; {a, 6}) when m = 3 and r > 6.
Then, for i G I, we have 0 < i < |a| — 4, and 4 < r — i < |a| — 1, so the walk
Ci = (a\ 6-1, a-( 1 a| -r+i-1), 6-1, a 1 a| -4, 6-1, a-( 1 a 1 -i-4), 6-1, ar-i-3, 6-2, a, 62, a, 6-2)
is as pictured in Figure 2. It is a hamiltonian cycle in Cay(G; a, 6) that covers S±1. Furthermore, since
a®6-1a-i = 6-1(6a®6-1 a-i) = 6-1[6-1,a-i] = 6-1[6, a]i = 6-1[a,6]-i, its voltage is of the form h2 [a, 6]-2i, where h2 is independent of i. Thus, we may let
{71,72} = { h2 [a, 6]-2i | i G I}.
Case 2. Assume m = 3. (Cf. [9, Case 4.3].) Since m and |a| both have at least one odd prime divisor, we must have m > 5 and |a| > 5. Let
X =
' (6-(m-2), a, 6m-3, a|a|-3, 6-1, (a-(|a|-4), 6-1, a|a|-4, 6-1)(m-3)/2) if |a| is odd, (6-1, (6-(m-3), a, 6m-3, a)(|a|/2)-1, 6-(m-2))	if |a| is even.
For each i with 1 < i < |_(M — 1)/2J, we have 1 < i < min(r — 1, |a| — 3) (since r > |a|/2 and |a| > 5), so we may let
Ci = (a\6-1 ,a-(|a|+i-r-1),X,a-(|a|-i-2),&-1,ar-i-1,&-(m-1)) (see Figures 3 and 4). Then Ci is a hamiltonian cycle in Cay(G; a, b).
106	ArsMath. Contemp. 7 (2014) 66-121
Figure 3: A hamiltonian cycle Gj in Cay(G; {a, b}) when m = |G/(a)| is odd.
Note that both possibilities for X contain oriented edges labelled a, b, and b-1. Furthermore, since |a| — i — 2 > 1, we see that Gj also contains at least one oriented edge labelled a-1. Therefore Gj covers {a, b, a-1, b-1} = S±1.
As in Case 1, the voltage nGj of Cj is of the form h2 [a, b]-2j, where h2 is independent of i. Since |a| > |G'| (see Lemma 3.4) and ([a, b]) = G' (see Lemma 3.5), Lemma 3.8 (combined with Lemma 3.6) tells us that for any x e N, we may choose i so that ((nGj)x) contains (G')2.	□
5 The main induction step
The induction step of our proof uses the following well-known gluing technique that is illustrated in Figure 5.
Definition 5.1. Let
•	C1 and C2 be two vertex-disjoint oriented cycles in Cay(G; S),
•	g e G, and
•	a, s e S.
If
•	G1 contains the oriented edge g(s), and
•	C2 contains the oriented edge gsa (s -1),
then we use C1 #a C2 to denote the oriented cycle obtained from C1 U C2 as in Figure 5, by
•	removing the oriented edges g(s) and gsa(s-1), and
E. Ghaderpour and D. W. Morris: Cayley graphs on nilpotent groups with...
67
1-1
1-2
a-1
Figure 4: A hamiltonian cycle Q in Cay(G; {a, 6}) when |a| is even.
• inserting the oriented edges g(a) and gsa(a-1). This is called the connected sum of C1 and C2.
Lemma 5.2. If C1, C2, g, s, and a are as in definition 5.1, and N C Z(G), then
n(Ci #a c2) = (nci)(nc2)[a, s]. Proof. Write Ci = gs(si)m=1 and C2 = ga(tj )n=1. Then
Ci #a C2 = gsa(a-1, (si)™-1, a, (jj-1),
so
(m—l\ l n— 1
H s J a ( ntj
m
n
1
n si sm[ a i n tj 1t
= a IJ_ J_si I sm a
\i=1 / \j=1
= a-1 (nc1) s—1 a (nc2) s
= (nc1) (nc2) a-1s—1as
= (nc1)(nc2) [a, s].
j n- 1
(ne, g n c z (g))
□
Corollary 5.3. Assume
•	2 < k < A and (to eliminate some subscripts) m = mk+1 and a = afc+1,
•	n1, n2,..., nm are elements of Vk,
b
b
106
ArsMath. Contemp. 7 (2014) 68-121
Figure 5: C1 and C2 are merged into a single cycle by replacing the two white edges labelled s and s—1 with the two black edges labelled a and a-1.
•	s1; s2,..., sm-1 are elements of Sk, and, for each i, a choice s* g {sf1} has been made in such a way that if sj+1 = s», then s*+1 = s*, and
•	N C Z(G).
Then there is a hamiltonian cycle in Cay(Gk+1; Sk+1) that covers S±+11, and whose voltage is
(m \ /m — 1	\
H n<J(n Mj .
Proof. For each i, let C» be an oriented hamiltonian cycle in Cay(Gk; Sk) that covers S±\ and has voltage n». We inductively construct sequences (g»)m=1 and (xi)m=1 of elements of Gk, as follows.
Let g1 = e. Since C1 covers S±\ we know there is some x1 g Gk, such that ag1C1 contains the oriented edge axl(sf).
Now, suppose g1, x1; g2, x2,..., gj; x» g Gk are given, such that the connected sum
ag1C1 a2g2G2 #S2 ••• #S|-1 ajgjGj
exists, and contains the oriented edge ajxj(s*). Since Cj+1 covers S±\ we know that Cj+1 contains an oriented edge labelled (s*)—1, and a different oriented edge that is labelled s*+1. Therefore, there exist gj+1, xj+1 g Gk, such that
aj+1gj+1Cj+1 contains the oriented edges aj+1xjs* ((s*) —^ and aj+1xj+1(s*+1). The first of these edges is removed when we form the connected sum
(ag1C1 #?. a2g2C2 #S2 ••• #Sj_1 ajgjCj) #S. a^V^,
E. Ghaderpour and D. W. Morris: Cayley graphs on nilpotent groups with...
69
but the second edge remains, and will be used to form the next connected sum (unless
i + 1 = m).
Since each Q is a hamiltonian cycle in Cay(Gk; Sk), the resulting connected sum
agiCi a	• • • , a"
passes through all of the vertices in aGk U a2Gk U • • • U amGk. That is, it passes through every element of Gk+i, so it is a hamiltonian cycle in Cay(Gk+i; Sk+i). Its voltage is calculated by repeated application of Lemma 5.2.
To complete the proof, we verify that the hamiltonian cycle covers S±+11. Since each Q covers S±, the disjoint union
agiGi U a2g2G2 U • • • U amgmGm
contains (at least) m disjoint pairs of edges labelled s and s_i, for each s g Sk. Each invocation of the connected sum removes only one such pair, and the operation is performed only m -1 times, so at least one of the m pairs must remain, for each s g Sk. Therefore, the hamiltonian cycle covers S±i. Also, the cycle certainly covers a±i, since each invocation of the connected sum inserts a pair of edges labelled a and a_i. Hence, the hamiltonian cycle covers S±i U{a±i} = S±+1.	□
We can now prove the main result of this section. (Recall that the condition a| is defined in Section 2.)
Proposition 5.4. Assume |N| is square-free and |G k+i/G 'k | is odd. Then
1.	a ' ^ a k+i, and
2.	a2+ ^ a2+i if | [s, t] | is even for all s, t g Sk+i with s = t.
Proof. For convenience, let m = mk+i and a = ak +i. Let hk g N be as in (a'), and choose an oriented hamiltonian cycle G in Cay(G k; Sk) that covers S±, and has its voltage in hk (Gk )e. There is no harm in assuming that the voltage is precisely hk. Let
hk+i = (hk)m[a,CTi];
2-1
Given any x g N, corollary 3.11 provides a sequence (si)™ii of elements of Sk, and
s* g {s±i} for each i, such that s*+i = s* whenever si+i = s4, and
"
(x (hk )m j[ [a, s*], (Gk yj contains (G'+i )e.	(5.5)
From (a|) we know there exists n g Vk n hk (Gk)% such that, if we let
m— i
Y = n (hk)m—i n [a, s*],
i=i
then (xy) contains (Gk)e. Since n = hk (mod (Gk)e), combining this with (5.5) shows that (xy) contains (Gk+i)e. Also, since we are assuming | [a, s*] | is even if e = 2, we have
[a, s*] = [a, ai] (mod (Gk+i)e) for all i, so
Y G (hk)m[a,ai]m—i(Gk+i)e = h^G^)6.
106
ArsMath. Contemp. 7 (2014) 70-121
Furthermore, corollary 5.3 tells us that there is a hamiltonian cycle in Cay(G; S) whose voltage is y, and this hamiltonian cycle covers . This establishes «k+1.
Now, if e = 2, then our assumptions imply that | hk | and | [a, o 1] | are both even. Since m and m - 1 are of opposite parity, this implies that |hk+1| is even, so (hk, (G'fc+1)2} contains G'fc+1. This establishes «k+r	^
6 Combining the base case with the induction step
Recall that the condition aek is defined in Section 2.
Corollary 6.1. Assume |N| is square-free and I > 2. If |G'| is odd, then « is true unless
|G'| = |s| = 3 for all s G S.
Proof. Assume it is not the case that |G'| = |s| = 3 for all s G S. Then we may assume (by permuting the elements of S) that either |G2| =3 or |a1| = 3. Therefore proposition 4.1 tells us that «2 is true. Also, since |G'| is odd, we have « ^ a1 (see remark 2.7(1)), so «2 is true. Then repeated application of proposition 5.4(1) establishes a|.	□
Proposition 6.2. Assume |N| is square-free and I > 3. If |G'| is even, then:
1.	«1 is true if there exist s, t G S, such that | [s, t] | is odd and s = t.
2.	«2+ is true if | [s, t] | is even for all s, t G S with s = t.
Proof. Since |G'| is even, we may assume (by permuting the elements of S) that | [a3, a1] | is even. It suffices to prove «3 or «3+ (as appropriate), for then repeated application of proposition 5.4 establishes the desired conclusion. Thus, we may assume I = 3, so G3 = G. Let m = m.3 and a = = o^.
By permuting the elements of S, we may assume that either:
odd case: | [o3, o2] | is odd, or even case: | [s, t] | is even for all s, t g S with s = t.
Furthermore, in the even case, we may assume that either:
even subcase: (or, 02} has even index in G, or
odd subcase: (s, t} has odd index in G, for all s, t g S, such that s = t.
Since | [o3, o1] | is even, we know |o1| is even (see Lemma 3.4). In particular, we have |o1| = 3, so proposition 4.1 tells us that «2 is true.
We now use a slight modification of the proof of proposition 5.4. Let h2 G N be as in («k) (with k = e = 2), and choose an oriented hamiltonian cycle C in Cay(G2; S2) that covers S^1, and has its voltage in h2(G2)2. There is no harm in assuming that the voltage is precisely h2.
Since |o1| is even, we know |G21 is even. Therefore, Lemma 3.15 provides a hamiltonian cycle C' in Cay(G2; S2), such that nC' is a generator of G2. Let
h	in the odd subcase of the even case,
in all other cases.
Let h3 = (h2)m-1h'[a,o1]m-1.
E. Ghaderpour and D. W. Morris: Cayley graphs on nilpotent groups with...
71
Given any x G N, corollary 3.11 provides a sequence (si )m=i1 of elements of S2, and
s* G jsf1} for each i, such that s*+1 = s* whenever si+1 = si; and
/	m-1	\
/ x(h2)m-1h' ^ [a, s*], (G2)M contains (G')2.	(6.3)
Furthermore, in the odd case, the choices can be made so that (6.3) holds with G' in the place of (G')2.
From «2, we know there exists n G V2 n h2 (G2)2, such that, if we let
m— 1
Y = n (h2)m—2h' H [a, s*], i=1
then
(xy) contains (G')2.	(6.4)
It is clear from the definitions that y G h3G3. Furthermore, we have y G h3(G3)2 in the even case.
corollary 5.3 tells us that there is a hamiltonian cycle in Cay(G; S) whose voltage is y, and this hamiltonian cycle covers S±1. We now consider various cases individually.
Case 1. The odd case. Recall that, in this case, (6.3) holds with G' in the place of (G')2. Since n = h2 (mod (G2)2), combining this with (6.4) shows that (xy) contains all of G'. This establishes a1..
Case 2. The even subcase of the even case. In this subcase, we know m is even, h' = h2, and |[a, a1]| is even. Since h3 = (h2)m[a, a1]m—1, we see that |h3| is even, so (h3, (G3)2) contains G3. This establishes a3+.
Case 3. The odd subcase of the even case. In this subcase, we know m — 1 is even, and h' = nC' has even order. Therefore |h31 is even, so (h3, (G3)2) contains G3. This establishes «3+.	^
We can now establish our main theorem:
Proof of theorem 1.2. We may assume:
•	I > 3, for otherwise proposition 3.16 applies.
•	|G| is not a power of 3, for otherwise theorem 3.13 applies.
Let S be a minimal generating set of G, and let N = G'. Note that S is a minimal generating set of G (because G' is contained in the Frattini subgroup $(G) [8, Thm. 10.4.3]).
We claim there is a hamiltonian cycle in Cay(G; S) whose voltage generates G'. While proving this, there is no harm in assuming that |G'| is square-free (see Lemma 3.14). Also note that, since |G| is not a power of 3, we cannot have |G'| = |s| = 3 for all s G S. Then, by applying either corollary 6.1 or proposition 6.2 (depending on the parity of |G'|), we obtain either «1 or a^. Each of these yields the desired hamiltonian cycle in Cay(G; S) (see Lemma 2.6).
Now that the claim has been verified, the Factor Group Lemma (2.5) provides a hamil-tonian cycle in Cay(G; S).	□
106
ArsMath. Contemp. 7 (2014) 72-121
References
[1]	B. Alspach, C. C. Chen and M. Dean, Hamilton paths in Cayley graphs on generalized dihedral groups,ArsMath. Contemp. 3 (2010), 29-47. MR2592513
[2]	B. Alspach and C. Q. Zhang, Hamilton cycles in cubic Cayley graphs on dihedral groups, Ars Combin. 28 (1989), 101-108. MR 1039136
[3]	C. C. Chen and N. Quimpo, On strongly hamiltonian abelian group graphs, in: K. L. McAvaney, ed., Combinatorial Mathematics VIII (Proceedings, Geelong, Australia 1980), Springer-Verlag, Berlin, 1981, pp. 23-24. MR 0641233
[4]	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
[5]	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
[6]	E. Durnberger, Every connected Cayley graph of a group with prime order commutator group has a Hamilton cycle, in: B. Alspach and C.Godsil, eds., Cycles in Graphs (Burnaby, B.C., 1982), North-Holland, Amsterdam, 1985, pp. 75-80. MR 0821506
[7]	D. Gorenstein, Finite Groups, Chelsea, New York, 1980, MR 0569209
[8]	M. Hall, Jr., Theory of Groups, Macmillan, New York, 1959. MR 0103215
[9]	K. Keating and D. Witte, On Hamilton cycles in Cayley graphs with cyclic commutator subgroup, in: B. Alspach and C.Godsil, eds., Cycles in Graphs (Burnaby, B.C., 1982), North-Holland, Amsterdam, 1985, pp. 89-102. MR 0821508
[10]	K. Kutnar and D. Marusic, Recent trends and future directions in vertex-transitive graphs, Ars Math. Contemp. 1 (2008), 112-125. MR 2443319
[11]	K.Kutnar, D.Marusic, D.W.Morris, J.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. MR0708161
[13]	D. W. Morris, 2-generated Cayley digraphs on nilpotent groups have hamiltonian paths, Con-trib. Discrete Math. 7 (2012), 41-47.
[14]	I. Pak and R. Radoicic, Hamiltonian paths in Cayley graphs, Discrete Math. 309 (2009), 55015508. MR2548568
[15]	D.Witte, On Hamiltonian circuits in Cayley diagrams, Discrete Math. 38 (1982), 99-108. MR0676525
[16]	D.Witte, Cayley digraphs of prime-power order are Hamiltonian, J. Combin. Theory Ser. B 40 (1986), 107-112. MR 0830597
[17]	D. Witte and J. A. Gallian, A survey: Hamiltonian cycles in Cayley graphs, Discrete Math. 51 (1984) 293-304. MR 0762322