Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 5 (2012) 189–215
Cayley graphs of order 16p are hamiltonian
Stephen J. Curran
Department of Mathematics, University of Pittsburgh at Johnstown
Johnstown, PA 15904, USA
Dave Witte Morris
Department of Mathematics and Computer Science, University of Lethbridge
Lethbridge, Alberta, T1K 3M4, Canada
Joy Morris
Department of Mathematics and Computer Science, University of Lethbridge
Lethbridge, Alberta, T1K 3M4, Canada
Received 4 April 2011, accepted 29 September 2011, published online 21 March 2012
Abstract
Suppose G is a finite group, such that |G| = 16p, where p is prime. We show that if
S is any generating set of G, then there is a hamiltonian cycle in the corresponding Cayley
graph Cay(G;S).
Keywords: Cayley graphs, hamiltonian cycles.
Math. Subj. Class.: 05C25, 05C45
1 Introduction
This paper establishes one of the cases of Theorem 1.2(1) of [10]. Namely, several of the
main results of that paper combine to show:
Every connected Cayley graph on G has a hamiltonian cycle
if |G| = kp, where p is prime, 1 ≤ k < 32, and k /∈ {16, 24, 27, 30}. (1.1)
We handle the first excluded case:
Theorem 1.1. If |G| = 16p, where p is prime, then every connected Cayley graph on G
has a hamiltonian cycle.
E-mail addresses: SJCurran@pitt.edu (Stephen J. Curran), Dave.Morris@uleth.ca (Dave Witte Morris),
Joy.Morris@uleth.ca (Joy Morris)
Copyright c© 2012 DMFA Slovenije
190 Ars Math. Contemp. 5 (2012) 189–215
Remark 1.2. The cases k = 27 and k = 30 are covered in [5, 6], but it seems that the case
k = 24 will be more difficult.
Here is an outline of the paper:
1. Introduction
2. Preliminaries on hamiltonian cycles in Cayley graphs
2.1. Factor Group Lemma
2.2. Generator in a cyclic, normal subgroup
2.3. Miscellaneous results
3. Groups without a normal Sylow p-subgroup
3.1. Groups of order 48
3.2. Groups of order 80
3.3. Groups of order 112
4. Preliminaries on groups of order 16p
5. The case where G/G′ ∼= Z2 × Z2
6. The case where G/G′ ∼= Z4 × Z2
7. The case where G/G′ ∼= Z2 × Z2 × Z2
Acknowledgments. We are grateful to the referee for reading the manuscript very carefully
and making numerous suggestions for improvement. This research was partially supported
by a grant from the Natural Sciences and Engineering Research Council of Canada. Most
of the work was carried out during a visit of S.J.C. to the University of Lethbridge.
2 Preliminaries on hamiltonian cycles in Cayley graphs
For ease of reference, we reproduce several useful results that provide hamiltonian cycles
in Cayley graphs.
Notation.
1. G always represents a finite group.
2. For S ⊂ G and s1, s2, . . . , sn ∈ S ∪ S−1, we use (s1, s2, s3, . . . , sn) to denote the
walk in Cay(G;S) that visits (in order) the vertices
e, s1, s1s2, s1s2s3, . . . , s1s2 · · · sn.
Also,
• (s1, s2, s3, . . . , sn)k denotes the walk that is obtained from the concatenation
of k copies of (s1, s2, s3, . . . , sn), and
• (s1, s2, s3, . . . , sn)# denotes the walk (s1, s2, s3, . . . , sn−1) that is obtained
by deleting the last term of the sequence.
Notation. For any group G, and any a, b ∈ G, we use:
S. J. Curran, D. Witte Morris and J. Morris: Cayley graphs of order 16p are hamiltonian 191
1. [a, b] to denote the commutator a−1b−1ab,
2. ba to denote the conjugate a−1ba,
3. G′ to denote the commutator subgroup [G,G] of G, and
4. Φ(G) to denote the Frattini subgroup of G.
See [7, §5.1] for some basic properties of the Frattini subgroup (and its definition).
2.1 Factor Group Lemma
The following elementary results are well known (and easy to prove).
Lemma 2.1 (“Factor Group Lemma” [13, §2.2]). Suppose
• N is a cyclic, normal subgroup of G,
• (s1, s2, . . . , sm) is a hamiltonian cycle in Cay(G/N ;S), and
• the product s1s2 · · · sm generates N .
Then (s1, s2, . . . , sm)|N | is a hamiltonian cycle in Cay(G;S).
Corollary 2.2. Suppose
• N is a cyclic, normal subgroup of G, such that |N | is a prime power,
• 〈s−1t〉 = N for some s, t ∈ S ∪ S−1, and
• there is a hamiltonian cycle in Cay(G/N ;S) that uses at least one edge labelled s.
Then there is a hamiltonian cycle in Cay(G;S).
Corollary 2.3. Suppose
• N is a cyclic, normal subgroup of G, such that |N | is a prime power,
• s ∈ S, with s2 ∈ N r Φ(N), and
• there is a hamiltonian cycle in Cay(G/N ;S) that uses at least one edge labelled s.
Then there is a hamiltonian cycle in Cay(G;S).
Lemma 2.4 ([10, Cor. 2.9]). Suppose
• S is a generating set of G,
• H is a subgroup of G, such that |H| is prime,
• the quotient multigraph H\Cay(G;S) has a hamiltonian cycle C, and
• C uses some double-edge of H\Cay(G;S).
Then there is a hamiltonian cycle in Cay(G;S).
192 Ars Math. Contemp. 5 (2012) 189–215
2.2 Generator in a cyclic, normal subgroup
Theorem 2.5 (Alspach [1, Cor. 5.2]). Suppose
• s and t are elements of G, and
• G = 〈s〉n 〈t〉.
Then Cay(G; s, t) has a hamiltonian cycle.
The following observation is well known.
Lemma 2.6 ([10, Lem. 2.27]). Let S generate G and let s ∈ S, such that 〈s〉 / G. If
• Cay
(
G/〈s〉;S
)
has a hamiltonian cycle, and
• either
1. s ∈ Z(G), or
2. |s| is prime,
then Cay(G;S) has a hamiltonian cycle.
Here is another similar result.
Lemma 2.7. Suppose
• s ∈ S, with 〈s〉 / G,
• |s| is a divisor of pq, where p and q are distinct primes,
• sp ∈ Z(G),
• |G/〈s〉| is divisible by q, and
• Cay
(
G/〈s〉;S
)
has a hamiltonian cycle.
Then there is a hamiltonian cycle in Cay(G;S).
Proof. We may assume |s| = pq and s /∈ Z(G), for otherwise Lemma 2.6 applies. Let
• (s1, . . . , sm) be a hamiltonian cycle in Cay
(
G/〈s〉;S
)
,
• g = s1s2 · · · sm be its endpoint in G, and
• k = |s|/|g|.
Consider the walk
(s1, s
k−1, s2, s
k−1, . . . , sm, s
k−1).
Writing s = xw, where x is the q-part of s and w is the p-part of s, and noting that
x ∈ Z(G) (because xp = sp ∈ Z(G)), we see that the endpoint is
s1(xw)
k−1s2(xw)
k−1 · · · sm(xw)k−1 = g x(k−1)m
∏
g′∈G/〈s〉
wg
′
= g, (2.1)
since m = |G/〈s〉| is divisible by q, and 〈w〉 ∩ Z(G) = {e}.
Therefore, the walk
(s1, s
k−1, s2, s
k−1, . . . , sm, s
k−1)|g|
is closed. Also (using (2.1)), it is not difficult to see that the walk traverses all of the
elements of G. Therefore, it is a hamiltonian cycle in Cay(G;S).
S. J. Curran, D. Witte Morris and J. Morris: Cayley graphs of order 16p are hamiltonian 193
2.3 Miscellaneous results
Theorem 2.8 (Marušič-Durnberger-Keating-Witte [9]). If G′ is a cyclic p-group, then ev-
ery connected Cayley graph on G has a hamiltonian cycle.
The proof in [12] yields the following result.
Theorem 2.9 ([11, Cor. 3.3]). Suppose
• S is a generating set of G,
• N is a normal p-subgroup of G, and
• st−1 ∈ N , for all s, t ∈ S.
Then Cay(G;S) has a hamiltonian cycle.
The following observation is also known, but we do not know whether it is in the
literature, so we provide a proof. Because it is of independent interest, we prove a more
general version than we need.
Lemma 2.10. Let S generate G, and let X be a subset of S. Assume:
• 〈X〉 is abelian (and nontrivial),
• for each g ∈ G, either g centralizes every element of 〈X〉, or g inverts every element
of 〈X〉,
• there is a hamiltonian cycle in Cay
(
〈X〉;X
)
, and
• there is a hamiltonian path in Cay(G/〈X〉;S).
Then there is a hamiltonian cycle in Cay(G;S).
Proof. Let
• [x0, x1, . . . , xm] be a hamiltonian cycle in Cay
(
〈X〉;X
)
,
• [g0, g1, . . . , gn] be a path in Cay(G;S) that is the lift of a hamiltonian path in
Cay
(
G/〈X〉;S
)
,
• C = Cay
(
Zm; {1}
)
be a cycle of length m,
• L be the path of length n with consecutive vertices 0, 1, . . . , n,
• f : V (C)× V (L)→ G be defined by
f(i, j) = xi gj .
Note that:
• for 0 ≤ i < m and 0 ≤ j < n, we have
f(i, j)−1 · f(i, j + 1) =
(
xi gj
)−1(
xi gj+1
)
= g−1j gj+1 ∈ S ∪ S
−1,
because gj and gj+1 are adjacent vertices in Cay
(
G;S
)
, and
• for 0 ≤ i < m and 0 ≤ j ≤ n, and letting x = x−1i xi+1 ∈ X ∪X−1, we have
f(i, j)−1 · f(i+ 1, j) =
(
xi gj
)−1(
xi+1 gj
)
= g−1j xgj = x
±1 ∈ X ∪X−1.
194 Ars Math. Contemp. 5 (2012) 189–215
Thus, f is an isomorphism from the Cartesian productC×L onto a subgraph of Cay(G;S).
Since the two graphs have the same number of vertices, it is a spanning subgraph. Then,
since it is easy to see that C × L has a hamiltonian cycle [3, Corollary on p. 29], we
conclude that Cay(G;S) has a hamiltonian cycle.
Remark 2.11. When we apply Corollary 2.2 or Corollary 2.3 to obtain a hamiltonian cy-
cle in Cay(G;S), and G has order 16p, the order of G/N is either 4p or 8p. Thus, (1.1)
provides a hamiltonian cycle in Cay(G/N ;S) with at least one edge labelled s. Simi-
larly, (1.1) provides a hamiltonian cycle in Cay(G/〈s〉;S) for Lemmas 2.6 and 2.7, and it
provides a hamiltonian path in Cay(G/〈X〉;S) for Lemma 2.10.
3 Groups without a normal Sylow p-subgroup
In this section, we prove Theorem 1.1 under the additional assumption that the Sylow p-
subgroups of G are not normal.
Proposition 3.1. If |G| = 16p, where p is prime, and the Sylow p-subgroups of G are not
normal, then every connected Cayley graph on G has a hamiltonian cycle.
We begin with the following result, which shows that there are only three possibilities
for the order of G.
Lemma 3.2. If |G| = 16p, where p is prime, and the Sylow p-subgroups of G are not
normal, then p ∈ {3, 5, 7}, so |G| ∈ {48, 80, 112}.
Proof. By Sylow’s Theorem [8, Thm. 15.7, p. 230], we know that the number of Sylow p-
subgroups is a divisor of 16, and is congruent to 1, modulo p. Since the only prime divisors
of 2− 1 = 1, 4− 1 = 3, 8− 1 = 7, and 16− 1 = 15 = 3× 5 are 3, 5, and 7, this implies
there is only one Sylow p-subgroup (which is normal) unless p ∈ {3, 5, 7}.
We now list the nine nonabelian groups of order 16, The list will be used repeatedly
in the remainder of the paper, because each of these nine groups arises as the Sylow 2-
subgroup of a group of order 16p.
Proposition 3.3 ([2, §118, p. 146]). There are nine nonabelian groups of order 16:
1. three groups with Q/Q′ ∼= Z2 × Z2:
(a) D16 (“dihedral”),
(b) Q16 (“generalized quaternion”), and
(c) Z2 n Z8 = 〈x〉n 〈y〉 with x−1yx = y3 (“semidihedral” or “quasidihedral”).
2. three groups with Q/Q′ ∼= Z4 × Z2:
(a) Z2 n Z8 = 〈x〉n 〈y〉 with x−1yx = y5,
(b) Z4 n Z4 = 〈x〉n 〈y〉 with x−1yx = y−1, and
(c) Z4 n (Z2 × Z2) = 〈x〉n 〈y, z〉 with x−1yx = yz and x−1zx = z.
3. three groups with Q/Q′ ∼= Z2 × Z2 × Z2:
(a) D8 × Z2 = 〈f, t | f2 = t4 = (ft)2 = e〉 × 〈z〉,
S. J. Curran, D. Witte Morris and J. Morris: Cayley graphs of order 16p are hamiltonian 195
(b) Q8 × Z2, and
(c) Z2 n (Z2 × Z4) = 〈x〉n 〈y, z〉 with x−1yx = yz2 and x−1zx = z.
The three possible orders of G are discussed individually in Propositions 3.4, 3.5
and 3.8 below.
3.1 Groups of order 48
Proposition 3.4 ([4]). If |G| = 48, and the Sylow 3-subgroups of G are not normal, then
every connected Cayley graph on G has a hamiltonian cycle.
Comments on the proof. A computer search can find hamiltonian cycles in all of these Cay-
ley graphs fairly quickly. Alternatively, a proof can be written by hand, but, unfortunately,
our presentation of this [4] is an unilluminating, 15-page case-by-case analysis, so we omit
the details.
It would be interesting to have a conceptual proof of Proposition 3.4, or, failing that, a
human-readable proof of only 2 or 3 pages.
3.2 Groups of order 80
Proposition 3.5. If |G| = 80, and the Sylow 5-subgroups of G are not normal, then every
connected Cayley graph on G has a hamiltonian cycle.
Proof. From Sylow’s Theorem (and the observation that 16 is the only nontrivial divisor
of 16 that is congruent to 1 modulo 5), we know there are 16 Sylow 5-subgroups. These
contain 16× 4 = 64 = |G| − 16 nonidentity elements of G, so the Sylow 2-subgroup must
be normal. Therefore G = Z5 nQ, where Q is the Sylow 2-subgroup. Since Z5 6/ G, we
know the action on Q is nontrivial.
We claim G is isomorphic to a semidirect product Z5 n (Z2)4. If not, then Q is not
elementary abelian, so Q/Φ(Q) has order 2, 4, or 8. Since groups of order 2, 4, or 8 have
no automorphisms of order 5, this implies that Z5 acts trivially on Q/Φ(Q). Therefore Z5
acts trivially on Q [7, Thm. 5.3.5]. This is a contradiction.
Now let S be a minimal generating set for G. Then S must contain an element x that
generates G/(Z2)4. Then |x| = 5, so, by passing to a conjugate, we may assume 〈x〉 = P .
Also, since |x| = 5, we know that x acts on (Z2)4 via a linear transformation whose
minimal polynomial is λ4 + λ3 + λ2 + λ + 1. Therefore, with respect to any basis of the
form {v, vx, vx2 , vx3},
x acts via multiplication on the right by the matrix A =
0 1 0 00 0 1 00 0 0 1
1 1 1 1
.
(This is “Rational Canonical Form.”)
Let s be another element of S. Then 〈x, s〉 has nontrivial intersection with (Z2)4. Since
GLk(2) does not have any elements of order 5 when k < 4, we know that x acts irreducibly,
so this implies that 〈x, s〉 contains all of (Z2)4. Therefore S = {x, s} (if S is minimal).
Obviously, s is of the form s = xiv, for some v ∈ (Z2)4 and (by passing to the inverse
if necessary) we may assume 0 ≤ i ≤ 2. If i = 1, then x−1s ∈ (Z2)4, so Theorem 2.9
applies. Thus, we may assume i ∈ {0, 2}. So
S = {x, v} or S = {x, x2v},
196 Ars Math. Contemp. 5 (2012) 189–215
and (by choosing an appropriate basis) v = (1, 0, 0, 0) ∈ (Z2)4.
Case 1. Assume S = {x, v}. We claim that a hamiltonian cycle in Cay(G;S) is given by:
x4, v, x−2, v, x, v, (x2, v)3, (x, v)2, x−2, v, x, v, x−1, v, (x2, v)2, x−2, v, x, v, x2, v,
x−2, v, (x−1, v)2, x, v, x2, v, x−2, v, x−1, v, x, v, (x2, v)2, (x−1, v)3, x2, v, x, v.
To verify this, we list the vertices of the cycle, using a, b, c, and d to denote the generators
of (Z2)4, where a = v, b = vx, c = bx = vx
2
, and d = cx = vx
3
. Then dx = vx
4
= abcd.
The hamiltonian cycle visits the vertices of Cay(G;S) in the order:
e, x, x2, x3, x4, bx4, bx3, bx2, bdx2, bdx3, bcdx3, bcdx4, bcd, abcd, abcdx, abcdx2, abcx2,
abcx3, abcx4, acx4, ac, c, cx, abdx, abd, abdx4, adx4, ad, d, dx4, bdx4, bd, bdx, acx, acx2,
acx3, ax3, ax2, ax, bcdx, bcdx2, bcx2, bcx3, bcx4, cx4, cx3, cx2, cdx2, cdx, abx, ab, b, bx,
acdx, acdx2, acdx3, adx3, adx2, adx, bcx, bc, abc, abcx, dx, dx2, dx3, cdx3, cdx4, cd,
acd, acdx4, abcdx4, abcdx3, abdx3, abdx2, abx2, abx3, abx4, ax4, a, e.
Case 2. Assume S = {x, x2v}. A hamiltonian cycle in the quotient multigraph P\Cay(G;
S) is given by:
x2v, x−1, (x2v)−1, x−4, x2v, x, (x2v)−1, x−1, (x2v)−1, x2, (x2v)2.
Again we use the notation a = v, b = vx, c = vx
2
, and d = vx
3
to list the vertices in this
hamiltonian cycle:
P, Pa, Pabcd, Pcd, Pbc, Pab, Pbcd, Pabc, Pb, Pc, Pad, Pabd, Pacd, Pac, Pbd, Pd, P.
The edge from Pac to Pbd is a double edge, coming from both x and x2v, so Lemma 2.4
provides a hamiltonian cycle in Cay(G;S).
3.3 Groups of order 112
Before finding a hamiltonian cycle in Cay(G;S), we prove two results that determine the
structure of G.
Lemma 3.6. If G is any group of order 112, then G has a normal Sylow subgroup.
Proof by contradiction. Assume G has no normal Sylow subgroups, and let P be a Sylow
7-subgroup of G. Let N be a minimal normal subgroup of G. Since G is solvable (for
example, this follows from Burnside’s paqb Theorem [7, Thm. 4.3.3]), N is an elementary
abelian normal subgroup of G. Since P is not normal, we must have |N | = 2k for some k.
Case 1. Assume k 6= 3. We know k 6= 4, since the Sylow 2-subgroups are not normal, so
k ∈ {1, 2}. Furthermore, we know that the Sylow 2-subgroups of G/N are not normal.
Observe that |G/N | is either 28 or 56.
We claim that PN / G. If not, then the Sylow 7-subgroup of G/N is not normal, so
|G/N | = 56 and G/N has eight Sylow 7-subgroups. Thus, there are |G/N | − |QN/N | =
56− 8 = 48 elements of order 7 in G/N . So G/N has only one Sylow 2-subgroup, which
must be normal. This contradicts the assumption that G has no normal Sylow subgroups.
S. J. Curran, D. Witte Morris and J. Morris: Cayley graphs of order 16p are hamiltonian 197
Since |PN | = 7|N | ∈ {14, 28}, we know P is normal (hence characteristic) in PN ,
so P / G. This contradicts the assumption that G has no normal Sylow subgroups.
Case 2. Assume k = 3. Then |G/(PN)| = 2, so PN / G. Since P does not centralize N
(otherwise P would be normal inG), it must act onN via a linear transformation of order 7.
Since there is no normal 7-complement, we know there is an element of G that normal-
izes P , but does not centralize it [7, Thm. 7.4.3]. So some element of G inverts P , which
means that every element of P is conjugate to its inverse.
However, if we let
• g be a generator of P ,
• A be the linear transformation induced by g on the vector space (Z2)3, and
• f(λ) be the minimal polynomial of A,
then f(λ) is an irreducible polynomial of degree 3. Since 3 is odd, the roots of f(λ) cannot
come in pairs, so there is some root α of f(λ) (in an extension field), such that α−1 is
not a root of f(λ). Therefore g and g−1 do not have the same minimal polynomial, so
g is not conjugate to g−1 in GL3(2). This contradicts the conclusion of the preceding
paragraph.
Corollary 3.7. If |G| = 112, and G has no normal Sylow 7-subgroup, then
G ∼=
(
Z7 n (Z2)3
)
× Z2,
where a generator of Z7 acts via multiplication on the right by the matrix
A =
0 1 00 0 1
1 1 0
 .
Proof. Let P be a Sylow 7-subgroup ofG. From Lemma 3.6, we know thatG has a normal
Sylow 2-subgroupQ, soG = P nQ. Since P 6/ G, we know that P acts nontrivially onQ,
so it also acts nontrivially on Q/Φ(Q) [7, Thm. 5.3.5].
Case 1. Assume Φ(Q) is trivial. Then Q ∼= (Z2)4, and a generator x of P acts by a linear
transformation. Since
|GL4(2)| = (24 − 1)(24 − 2)(24 − 22)(24 − 23)
is not divisible by 72, we know that all subgroups of order 7 in GL4(2) are conjugate, so
the semidirect product Z7 n (Z2)4 is unique. Therefore G must be as described.
Case 2. Assume Φ(Q) is nontrivial. Since 7 - (2i − 1) for 1 ∈ {1, 2}, we must have
|Q/Φ(Q)| = 23. (So Φ(Q) = Q′ has order 2.) Therefore, a generator x of P acts transi-
tively on the nonidentity elements of Q/Φ(Q).
If Q is nonabelian, then Q is one of the groups listed in Proposition 3.3(3), since
Q/Q′ ∼= (Z2)3. In each of these groups, Φ(Q) is a proper subgroup of Z(Q). Thus
Z(Q)/Φ(Q) is a proper subspace of Q/Φ(Q); a contradiction.
Therefore Q is abelian. Then we see that every element of Q has order 2, for otherwise
the elements of order 2 in Q provide an invariant, proper subspace of Q/Φ(Q). This
contradicts the fact that Φ(Q) is nontrivial.
198 Ars Math. Contemp. 5 (2012) 189–215
Proposition 3.8. If |G| = 112, and the Sylow 7-subgroups are not normal, then every
connected Cayley graph on G has a hamiltonian cycle.
Proof. Corollary 3.7 provides an explicit description of G. Let
• x be a generator of P = Z7,
• v = (1, 0, 0) ∈ (Z2)3, and
• z be a generator of Z(G) ∼= Z2.
Case 1. Assume #S = 2. Let s be an element of S that is not in Q. Replacing s by a
conjugate, we may assume s is either x or xz.
Since |x| = 7, we know that the minimal polynomial of x is a divisor of
λ6 + λ5 + λ4 + λ3 + λ2 + λ+ 1 = (λ3 + λ+ 1)(λ3 + λ2 + 1) (over Z2).
So the minimal polynomial of x is either λ3 + λ + 1 or λ3 + λ2 + 1. Since (as explained
in the proof of Lemma 3.6), the minimal polynomials of x and x−1 are not the same,
we may assume (by replacing x with x−1 if necessary) that the minimal polynomial of x is
λ3+λ+1. Then (for any basis of the form {v, vx, vx2}), x acts on (Z2)3 via multiplication
on the right by the matrix A in the statement of Corollary 3.7. (This is “Rational Canonical
Form.”)
Let t be the other element of S. We have t = xivzj for some i and j, where v =
(1, 0, 0) ∈ (Z2)3. We may assume i ∈ {0, 1, 2, 4} (by replacing t with its inverse if
necessary). Consider the basis {a, b, c} of (Z2)3 where
a = v, b = vx, and c = bx = vx
2
.
Then G is given by
G =
〈
a, b, c, x, z
∣∣∣∣∣ a2 = b2 = c2 = x7 = z2 = e, ab = ac = az = a,bc = bz = b, cz = c, ax = b, bx = c, cx = ab, xz = x
〉
Let ψ : G→ G be the homomorphism defined by
ψ(a) = bc, ψ(b) = ac, ψ(c) = b, ψ(x) = abcxz, and ψ(z) = z.
One can show that the relations of the group are preserved by ψ and that ψ is onto. Thus ψ
is an automorphism of G that sends the pair (x4v, x) to (x, x2v); so we may assume i 6= 4.
Also, if i = 1, then Theorem 2.9 applies. Thus, the generating sets to consider are:
• S = {x, vz},
• S = {x, x2vz},
• S = {xz, v},
• S = {xz, vz},
• S = {xz, x2v},
• S = {xz, x2vz}.
S. J. Curran, D. Witte Morris and J. Morris: Cayley graphs of order 16p are hamiltonian 199
In all cases, x acts on (Z2)3 via multiplication on the right by the matrix A, with respect to
the basis {a, b, c}.
Subcase 1.1. Assume S = {x, vz}. A hamiltonian cycle in Cay(G/〈z〉;S) is given by:(
x−1, vz, x, vz, x4, vz, x, vz, x2, vz, x−2, vz, x−3, vz, (x−4, vz)2,
x−3, vz, x, vz, x2, vz, x3, vz, x−2, vz, (x, vz)2, x−3, vz, x−1
)
.
To verify this, we list the vertices (according to a coset representative of 〈z〉) in the order
they are visited:
e, x6, bx6, b, ab, abx, abx2, abx3, abx4, x4, x5, cx5, cx6, c, ac, acx6,
acx5, ax5, ax4, ax3, ax2, bcx2, bcx, bc, bcx6, bcx5, bx5, bx4, bx3, bx2, bx, abcx,
abc, abcx6, abcx5, abx5, abx6, ax6, a, ax, cx, cx2, cx3, cx4, abcx4, abcx3, abcx2, x2,
x3, bcx3, bcx4, acx4, acx3, acx2, acx, x, e.
Since z is in the center of G, and the generator vz is used an odd number of times in
the hamiltonian cycle (specifically, 17 times), the endpoint in G is z, so the Factor Group
Lemma (2.1) provides a hamiltonian cycle in Cay(G;S).
Subcase 1.2. Assume S = {x, x2vz}. A hamiltonian cycle in P\Cay(G;S) is:(
x2vz, x−1, x2vz, x, (x2vz, x−1)2, (x2vz)−2, x, x2vz, x, (x2vz)3
)
.
It passes through the vertices of the quotient multigraph in the order:
P, Paz, Pacz, Pab, Pbc, Pcz, Pbz, Pb, Pa, Pz, Pabc, Pac, Pabz, Pbcz, Pc, Pabcz, P.
The edge between Pbz and Pb is a double edge, coming from both x2vz and (x2vz)−1, so
Lemma 2.4 provides a hamiltonian cycle in Cay(G;S).
Subcase 1.3. Assume S = {xz, v}. A hamiltonian cycle in P\Cay(G;S) is:(
xz, v, (xz)4, v, xz, v, (xz)−1, v, xz, v, (xz)2, v
)
.
It passes through the vertices of the quotient multigraph in the order:
P, Pz, Paz, Pb, Pcz, Pab, Pbcz, Pabcz, Pac, Pc, Pbz, Pabz, Pbc, Pabc, Pacz, Pa, P.
The edge between P and Pz is a double edge, coming from both xz and (xz)−1, so
Lemma 2.4 provides a hamiltonian cycle in Cay(G;S).
Subcase 1.4. Assume S = {xz, vz}. A hamiltonian cycle in P\Cay(G;S) is:(
xz, vz, (xz)2, vz, (xz)−1, vz, (xz)−2, vz, ((xz)−1, vz)3
)
.
It passes through the vertices of the quotient multigraph in the order:
P, Pz, Pa, Pbz, Pc, Pacz, Pabc, Pbcz, Pab, Pcz, Pac, Pabcz, Pbc, Pabz, Pb, Paz, P.
The edge between P and Pz is a double edge, coming from both xz and (xz)−1.
Subcase 1.5. Assume S = {xz, x2v}. A hamiltonian cycle in P\Cay(G;S) is:(
xz, x2v, (xz)2, (x2v, xz)2, (xz)2, x2v, xz, x2v, (xz)−2, (x2v)−1
)
.
200 Ars Math. Contemp. 5 (2012) 189–215
It passes through the vertices of the quotient multigraph in the order:
P, Pz, Paz, Pb, Pcz, Pabcz, Pac, Pab, Pbcz, Pabc, Pacz, Pabz, Pbc, Pc, Pbz, Pa, P.
The edge between P and Pz is a double edge, coming from both xz and (xz)−1, so
Lemma 2.4 provides a hamiltonian cycle in Cay(G;S).
Subcase 1.6. Assume S = {xz, x2vz}. A hamiltonian cycle in P\Cay(G;S) is:(
(xz, x2vz)5, (xz)5, (x2vz)−1
)
.
It passes through the vertices of the quotient multigraph in the order:
P, Pz, Pa, Pbz, Pb, Pcz, Pabc, Pacz, Pab, Pbcz, Pc, Pabz, Pbc, Pabcz, Pac, Paz, P.
The edge between P and Pz is a double edge, coming from both xz and (xz)−1, so
Lemma 2.4 provides a hamiltonian cycle in Cay(G;S).
Case 2. Assume #S > 2. Every minimal generating set of G/Z(G) ∼= Z7 n (Z2)3 has
only 2 elements, so there exist s, t ∈ S, such that 〈s, t〉 = 〈x, v〉. We may assume s = x.
And we have t = xiv.
Since 〈s, t〉 has index 2 in G, we must have #S = 3; let u be the third element of S, so
u = xjwz with w ∈ (Z2)3.
• Since 〈x, xjwz〉 = 〈s, u〉 6= G, we must have w = e. So u = xjz.
• Then we must have j = 0, for otherwise 〈u〉 = 〈x, z〉 3 x = s, which contradicts
the fact that S is a minimal generating set.
But then u = z ∈ Z(G), so Lemma 2.6(1) and Remark 2.11 apply.
4 Preliminaries on groups of order 16p
Because of Proposition 3.1, we henceforth
assume that the Sylow p-subgroups of G are normal.
Notation. Throughout the remainder of this paper:
• G is a group of order 16p, where p is an odd prime,
• P ∼= Zp is a Sylow p-subgroup of G (and P / G),
• Q is a Sylow 2-subgroup of G, so |Q| = 16, and
• S is a minimal generating set of G.
We wish to show Cay(G;S) has a hamiltonian cycle.
We know P ∼= Zp, and the possibilities for Q are given in Proposition 3.3.
Lemma 4.1. We may assume:
1. G = Qn P ,
2. Q is nonabelian, and acts nontrivially on P ,
S. J. Curran, D. Witte Morris and J. Morris: Cayley graphs of order 16p are hamiltonian 201
3. G′ = Q′ × P is cyclic.
Proof. (1) Since P / G, G = QP , and Q ∩ P = {e}, we have G ∼= Qn P .
(2, 3) Since the automorphism group of P ∼= Zp is abelian, we know Q′ centralizes P .
So (1) implies that Q′ ≤ G′ ≤ Q′ × P . Since all of the groups in Proposition 3.3 have
a cyclic commutator subgroup, we know Q′ is cyclic. Also, by Theorem 2.8, we may
assume G′ is not a cyclic subgroup of prime-power order. Thus, we may assume G′ 6= Q′
andG′ 6= P . SoG′ = Q′×P (andQ′ 6= {e}, soQ is nonabelian). SinceQ′ and P are both
cyclic, this implies G′ is cyclic. Furthermore, since P ⊂ G′, we know that G 6∼= Q×P , so
the action of Q on P is nontrivial.
The following corollary shows there are three possibilities for G/G′; each of these
possibilities will be considered individually, in Sections 5, 6 and 7, respectively.
Corollary 4.2. We may assume G/G′ is isomorphic to either Z2 × Z2, Z4 × Z2, or Z2 ×
Z2 × Z2.
Proof. Since G = QP and G′ = Q′P (see Lemma 4.1), we have G/G′ ∼= Q/Q′. Then
the desired conclusion follows from inspection of Proposition 3.3.
Corollary 4.3. We may assume
1. Q′ / G,
2. Q′ ≤ Φ(G), and
3. S is a minimal generating set of G/Q′.
Proof. (1) From Lemma 4.1(3), we know that Q′ is normalized by P (indeed, it is central-
ized by P ). Then, since it is also normalized by Q, it is normalized by PQ = G.
(2) Let M be a maximal subgroup of G.
• If M contains P , then M/P is a maximal subgroup of G/P , so M/P contains
Φ(G/P ) = Φ(Q)P/P ≥ Q′P/P , so M ≥ Q′.
• If M does not contain P , then M is a 2-group, so the maximality implies it is a
Sylow 2-subgroup ofG. Every Sylow 2-subgroup (such asM ) contains every normal
2-subgroup (such as Q′), so M ≥ Q′.
Thus, every maximal subgroup of G contains Q′, so Q′ ≤ Φ(G).
(3) Since S is a minimal generating set of G, this follows from (2).
Corollary 4.4. If G = 〈a, b〉 is 2-generated, then G′ = 〈[a, b]〉.
Proof. By Lemma 4.1(3), G′ is cyclic. Since every subgroup of a cyclic, normal subgroup
is normal, we know 〈[a, b]〉 / G. Since 〈a, b〉 = G, and a commutes with b in G/〈[a, b]〉,
we know G/〈[a, b]〉 is abelian, so G′ ⊂ 〈[a, b]〉. The opposite inclusion is obvious.
202 Ars Math. Contemp. 5 (2012) 189–215
5 The case where G/G′ ∼= Z2 × Z2
Proposition 5.1. Assume |G| = 16p. If G/G′ ∼= Z2 × Z2, then Cay(G;S) has a hamilto-
nian cycle.
Proof. We proceed via case-by-case analysis.
Case 1. Assume #S = 2. Write S = {a, b}. Then (a−1, b−1, a, b) is a hamiltonian
cycle in Cay(G/G′;S) whose endpoint in G is a−1b−1ab = [a, b]. This generates G′ (see
Corollary 4.4), so the Factor Group Lemma (2.1) applies.
Case 2. Assume #S ≥ 3. Since |G/Q′| = 4p is a product of only 3 primes, Corol-
lary 4.3(3) implies #S ≤ 3. Therefore #S = 3; write
S = {a, b, c}.
Subcase 2.1. Assume |c| is divisible by p. Since |G/Q′| is a product of only 3 primes,
and P is the unique subgroup of order p in G, the minimality of S (and Corollary 4.3(3))
implies
• the image of 〈c〉 in G/Q′ has order p, and
• the image of 〈a, b〉 in G/Q′ has order 4.
Thus, b has order 2 in G/Q′, so b either centralizes P or inverts it: let  ∈ {±1} such that
wb = w for all w ∈ P . Since Q′ is a cyclic group of order 4, its only automorphisms are
the identity automorphism and the one that inverts every element in Q′. Let ′ ∈ {±1},
such that ub = u
′
for all u ∈ Q′. Write c = uw for some u ∈ Q′ and w ∈ P . Then
cb = u
′
w = cu
′− ∈ cΦ(Q′) since ′ −  ∈ {0,±2}.
Now
(a−1, c−(p−1), b−1, cε(p−1), a, c−(p−1), b, cε(p−1))
is a hamiltonian cycle in Cay
(
G/Q′;S
)
whose endpoint in G/Φ(Q′) is
a−1c−(p−1)b−1cε(p−1)ac−(p−1)bcε(p−1) = a−1b−1ab = [a, b],
which generates Q′ (see Corollary 4.4). So the Factor Group Lemma (2.1) provides a
hamiltonian cycle in Cay(G;S).
Subcase 2.2. Assume no element of S has order divisible by p. This implies that
every element of S is a 2-element. Also, since Q/Q′ is a Sylow 2-subgroup of G/Q′, and
Q/Q′ ∼= G/G′ ∼= Z2 × Z2, we know that G/Q′ has no elements of order 4. Therefore
every element of S has order 2 in G/Q′.
So we may assume every element of S has order 2 inG/Φ(Q′), for otherwise Corollary 2.3
and Remark 2.11 apply with N = Q′. Then we may assume
every element of S has order 2,
for otherwise Corollary 2.3 and Remark 2.11 apply with N = Φ(Q′).
S. J. Curran, D. Witte Morris and J. Morris: Cayley graphs of order 16p are hamiltonian 203
Since G/P ∼= Q is a 2-generated 2-group, we know that all of its minimal generating
sets have the same cardinality, so some 2-element subset of S generates G/P . Since two
elements of order 2 always generate a dihedral group, we conclude that
Q ∼= D16 = 〈f, t|f2 = t8 = (ft)2 = e〉.
Subsubcase 2.2.1. Assume no element of S centralizes P . Let S be the image of S
in
G/Q′ ∼= (Z2 × Z2) n Zp ∼= D4p.
From Corollary 4.3(3), we see that S is a minimal generating set of D4p. Also, by the
assumption of this subsubcase, we know that every element of S is a reflection; let f ∈ S.
There are only two proper subgroups of D4p that properly contain 〈f〉 (because Z2 and Zp
are the only nontrivial proper subgroups of the group Z2p of rotations), so we may assume
S = {f, fx, fy}, where x and y are rotations of orders 2 and p in D4p, respectively. Then
〈fx, fy〉 = D4p, which contradicts the minimality of S.
Subsubcase 2.2.2. Assume S contains an element that centralizes P . Each element
of S must map to a reflection in G/P ∼= Q ∼= D16 (since the elements of S all have order 2
in both G/P and G/(Q′P )). Then, by the assumption of this subsubcase, we know that
some reflection centralizes P . Because Q acts nontrivially on P , we have
G = 〈f, t, w | f2 = t8 = wp = e, ftf = t−1, fwf = w, t−1wt = w−1〉.
From the assumption of this subsubcase, we may assume f ∈ S. By the minimality of S,
we must have 〈f, s〉 = Q, for some s ∈ S (after replacing Q by a conjugate). Since all
elements of S ∩ Q are reflections, we may assume s = ft. To generate G (and map to
a reflection in G/P ), the final element of S must be of the form ftiwj , with p - j. By
replacing w with wj , we may assume j = 1. So the final element of S is ftiw. Since all
elements of S have order 2 in G, it must be the case that ti inverts w, so i is odd. So
S is of the form {f, ft, ftiw}, with i odd.
By Corollary 4.3(1), we know Q′ / G. Observe that the image of f is central in G/Q′,
and ftiw ≡ ftw (mod Q′) (because Q′ = 〈t2〉 and i is odd), so
Cay(G/Q′;S) ∼= Cay
(
〈ft, ftiw〉/Q′; {ft, ftiw}
)
× Cay
(
〈f〉; {f}
) ∼= C2p ×K2
is a prism, which has the natural hamiltonian cycle
(
(ft, ftiw)p#, f
)2
. The endpoint in G
is ((
(ft)(ftiw)
)p
(ftiw)−1f
)2
=
(
(ti−1w)pw−1t−i
)2
=
(
t(i−1)p−iw−1
)2
= t2(i−1)p−2i.
Since i is odd, the exponent of t is congruent to 2 modulo 4, so the endpoint gener-
ates 〈t2〉 = Q′. Thus, the Factor Group Lemma (2.1) provides a hamiltonian cycle in
Cay(G;S).
204 Ars Math. Contemp. 5 (2012) 189–215
6 The case where G/G′ ∼= Z4 × Z2
Proposition 6.1. Assume |G| = 16p. If G/G′ ∼= Z4 × Z2, then Cay(G;S) has a hamilto-
nian cycle.
Proof. We proceed via case-by-case analysis.
Case 1. Assume #S = 2. Let
• S = {a, b}, with a of order 4 in G/G′, and
• k ∈ Z with ga = gk for g ∈ G′.
Then (a−3, b−1, a3, b) is a hamiltonian cycle in G/G′, and its endpoint in G is
[a3, b] = [a, b]a
2
[a, b]a[a, b] = [a, b]k
2
[a, b]k[a, b] = [a, b]k
2+k+1.
By Corollary 4.4, this generates G′ unless gcd(k2 +k+ 1, |G′|) > 1. Since |G′| = 2p, and
k2 +k+ 1 is always odd, this generates G′ unless k2 +k+ 1 ≡ 0 (mod p), which implies
k3 ≡ 1 (mod p). This means that a3 centralizes P . But a4 ∈ G′ ≤ CG(P ), so this
implies that a centralizes P : therefore k ≡ 1 (mod p). Since k2 + k + 1 ≡ 0 (mod p),
we conclude that
p = 3 and a centralizes P .
From Lemma 4.1(2) (and the fact that a centralizes P ), we know that
b does not centralize P .
Since G′ = Q′P is cyclic of order 6, we know G′ has only two automorphisms; namely,
the identity automorphism and the automorphism that inverts G′. Thus xb = x−1 for
all x ∈ G′. If b has order 4 in G/G′, then the hamiltonian cycle (b−3, a−1, b3, a) in
Cay(G/G′;S) has endpoint
[b3, a] = [b, a]b
2
[b, a]b[b, a] = [b, a][b, a]−1[b, a] = [b, a]
in G, which generates G′. Thus Cay(G;S) has a hamiltonian cycle by the Factor Group
Lemma (2.1). So we may assume that b has order 2 in G/G′. Write b = qw for some
q ∈ Q and w ∈ P , where q−1wq = w−1. Then b2 = q2wqw = q2. Hence, the order
of b is not divisible by p, so b is a 2-element. Thus, we may assume (after replacing Q by
a conjugate) that b ∈ Q. Thus, the order of b in G/Q′ is 2. So we may assume |b| = 2, for
otherwise Corollary 2.3 and Remark 2.11 apply.
Since b ∈ Q, and 〈a, b〉 = G, we know a /∈ Q. Since a centralizes P , this implies
that |a| is divisible by p (i.e., 3). But |a| is also a multiple of 4 (its order in G/G′). So |a|
is divisible by 12. Since |G| = 16p = 48 (and G is not cyclic), this implies |a| is either
12 or 24. If |a| = 24, then G = 〈b〉 n 〈a〉, so Theorem 2.5 applies. So we may assume
|a| = 12.
Now, of the three groups listed in Proposition 3.3(2),
• group (2a) has no generating set without an element of order 8, and
• group (2b) has no 2-element generating set with an element of order 2.
S. J. Curran, D. Witte Morris and J. Morris: Cayley graphs of order 16p are hamiltonian 205
So Q must be group (2c), and we may assume a = xw (by relabeling the elements of Q).
Since 〈a, b〉 = G, we know 〈x, b〉 = Q, so (since |b| = 2), we may assume b = y (by
further relabeling the elements of Q). Note that, since z ∈ Z(G), we know z centralizes
both a and b.
Let N = 〈a2〉 = 〈x2, w〉, and consider the hamiltonian cycle
(
(b, a)4#, a−1
)
in
Cay(G/N ;S), which passes through the vertices in the following order:
N,Ny,Nxyz,Nxz,Nz,Nyz,Nxy,Nx,N.
Its endpoint in G is
(ba)4a−2 = (yxw)4a−2 = e · a−2 = a−2,
which generates 〈a2〉 = N . So the Factor Group Lemma (2.1) provides a hamiltonian cycle
in Cay(G;S).
Case 2. Assume #S > 2. Since G/G′ ∼= Z4 × Z2, there exists a 2-element subset {a, b}
of S that generates G/P . Since {a, b} ( S, and S is minimal, we have P 6⊂ 〈a, b〉.
Therefore, by passing to a conjugate, we may assume 〈a, b〉 = Q.
Let c be a third element of S (so c /∈ Q). Then 〈a, b, c〉 properly contains Q. But Q is a
maximal subgroup of G (since |G/Q| = p is prime), so this implies 〈a, b, c〉 = G. So the
minimality of S implies S = {a, b, c}.
Claim 6.2. We may assume, for each s ∈ S, that either s2 ∈ P , or sP ∈ Φ(Q)P , or s acts
on P via an automorphism of order 4.
Suppose there exists s ∈ S that has none of the three properties. Since #S > 2 and
sP /∈ Φ(Q)P , we know p - |s|, so (up to conjugacy) s ∈ Q. Then, since Q/Z(Q) ∼=
Z2 × Z2, we have s2 ∈ Z(Q), so 〈s2〉 / Q. Also, since s does not act on P by an
automorphism of order 4, we know s2 centralizes P . Therefore s2 ∈ Z(G), so 〈s2〉 / G,
Hence, Corollary 2.3 and Remark 2.11 apply.
Subcase 2.1. Assume Q ∼= Z4 n Z4 = 〈x〉 n 〈y〉. Since some element of S must
generate G/(〈y〉P ), we may assume x ∈ S (after replacing Q by a conjugate). That is, we
may assume a = x.
Observe that x2 6∈ P and xP 6∈ Φ(Q)P . Thus, the Claim tells us that x acts on P
via an automorphism of order 4. Hence, Q/CQ(P ) ∼= Z4. Therefore, CQ(P ) is a cyclic
normal subgroup of Q with a cyclic quotient, so we may assume CQ(P ) = 〈y〉.
Since Q has no 2-element generating set that contains an element of order 2, we know
|b| > 2. Therefore, from the Claim, we know that b generates Q/CQ(P ) = Q/〈y〉. So
b ≡ a±1 (mod 〈y〉); assume (by replacing b with its inverse if necessary) that ba ∈ 〈y〉.
Then, since 〈a, b〉 = Q, we must have 〈ba〉 = 〈y〉 / G. Then, since |y| = 4, Corollary 2.2
and Remark 2.11 apply.
Subcase 2.2. Assume c /∈ Φ(Q)P . Since Q does not centralize P , we may assume
b does not centralize P . Write c = wu for some w ∈ P and u ∈ Q. Since c 6∈ Q, we have
w 6= e. Since b does not centralize P , we have (w−1)b 6= w−1. Thus
[b, c] = (u−1)b(w−1)bwu = (u−1)bu((w−1)bw)u,
where (u−1)bu ∈ Q, ((w−1)bw)u ∈ P , and ((w−1)bw)u 6= e. Hence, [b, c] 6∈ Q′ and
[b, c] ∈ G′ = Q′ × P . Thus the order of [b, c] is a divisor of |G′| = 2p, but not a divisor
206 Ars Math. Contemp. 5 (2012) 189–215
of |Q′| = 2. Hence, p divides the order of [b, c] and we must have P ⊂ 〈[b, c]〉. If c ∈
{a, ab}Φ(Q)P , then 〈b, c〉 = Gwhich contradicts the minimality of S. Thus c ∈ bΦ(Q)P .
(But we may assume c /∈ b±1P , for otherwise Corollary 2.2 and Remark 2.11 apply.) Since
c 6∈ aΦ(Q)P , the argument of the preceding paragraph (by interchanging a and b) implies
that a must centralize P . That is, a ∈ CQ(P ). Therefore, the Claim implies |a| = 2. In
summary, we know:
• |a| = 2, and a centralizes P ,
• b does not centralize P , and
• c ∈ bΦ(Q)P , but c /∈ b±1P .
Subsubcase 2.2.1. Assume Q ∼= Z2 n Z8 = 〈x〉 n 〈y〉. Since |a| = 2, we may
assume a = x. Then we must have |b| = 8, so we may assume b = y. Then Φ(Q) = 〈b2〉,
so c ∈ {b3, b5}P . By replacing c with its inverse, we may assume c ∈ b5P . Then
S = {a, b, c} with a = x, b = y, and c = y5w, where w generates P .
Also, from the above properties of a and b, we know x centralizes P , but y acts on P via
an automorphism of order 4.
Consider the hamiltonian cycle
(b2, c−1, b2, c, b−1, a, b−7, a)
in Cay(G/P ;S), which passes through the vertices of the graph in the order:
P, Py, Py2, Py5, Py6, Py7, Py4, Py3, Pxy7, Pxy6, Pxy5, Pxy4,
Pxy3, Pxy2, Pxy, Px, P.
Note that, since the action of y on P has order 4, we know that y2 invertsw, so the endpoint
in G is
b2c−1b2cb−1ab−7a = y2(w−1y−5)y2(y5w)y−1xy−7x = y2w−1y2wy−1xyx = w2,
which generates P = 〈w〉. By the Factor Group Lemma (2.1), we have a hamiltonian cycle
in Cay(G;S).
Subsubcase 2.2.2. Assume Q ∼= Z4 n (Z2 × Z2) = 〈x〉 n 〈y, z〉. Since |a| = 2,
we may assume a = y. Then we may assume b = x. Since Φ(Q) = 〈b2, z〉, we must have
c ∈ {bz, b−1z}P . By replacing c with its inverse, we may assume c ∈ bzP . Then
S = {x, y, xzw}, where w generates P .
And y centralizes P , but x acts on P via an automorphism of order 4.
Let k ∈ Zp, such that x−1wx = wk. Since the action of x on P has order 4, we have
2 ≤ k ≤ p− 2. Consider the hamiltonian cycle
(xzw, x3, y, x2, xzw, x3, xzw, y, x−3)
S. J. Curran, D. Witte Morris and J. Morris: Cayley graphs of order 16p are hamiltonian 207
in Cay(G/P ;S) that passes through the vertices of this graph in the order:
P, Pxz, Px2z, Px3z, Pz, Pyz, Pxy, Px2yz, Px3yz, Py, Pxyz, Px2y,
Px3y, Px3, Px2, Px, P.
The endpoint of this cycle in G is
(xzw)(x3yx3zw)(x4zw)(yx−3) = (xzw)(x2yw)(zw)(xyz)
= x4y2z4w−kwkwk = wk.
Since k is coprime to p (recall 2 ≤ k ≤ p − 2), this generates P = 〈w〉. By the Factor
Group Lemma (2.1), we have a hamiltonian cycle in Cay(G;S).
Subcase 2.3. Assume c ∈ Φ(Q)P . We may assume c /∈ G′, for otherwise Lemma 2.7
applies.
Subsubcase 2.3.1. Assume Q ∼= Z2 n Z8 = 〈x〉 n 〈y〉. Up to automorphism, any
2-element generating set of Q is of the form {xyi, y}. Since xy4 has order 2, it may be
replaced with x (if i ∈ {3, 4, 5}). This implies that we may assume −2 ≤ i ≤ 2. Then,
since we may replace y with y−1, we may assume 0 ≤ i ≤ 2. However, xy2 has order 4,
but its square is in Q′, so it cannot act on P by an automorphism of order 4; therefore, the
Claim implies it is not in S. So i ∈ {0, 1}.
Since Φ(Q) = 〈y2〉 andQ′ = 〈y4〉, we must have c ∈ {y2, y6}P ; replacing c with c−1,
we may assume c ∈ y2P . Thus, either
S = {x, y, y2w} or S = {xy, y, y2w}, where 〈w〉 = P .
Also:
• x either centralizes P or inverts it, and
• y acts on P by an automorphism of order 4.
Let  ∈ {±1} such that x−1wx = w, and let k ∈ Zp such that y−1wy = wk. Since the
action of y on P has order 4, we have 2 ≤ k ≤ p− 2. Let N = 〈y4, P 〉 = 〈y4w〉 ∼= Z2p.
For the first generating set,
(y2w, y−1, y2w, x, y−3, x)
is a hamiltonian cycle in Cay(G/N ;S) that passes through the vertices of this graph in the
order:
N,Ny2, Ny,Ny3, Nxy3, Nxy2, Nxy,Nx,N.
The endpoint of this cycle in G is
y2wywxy−3x = y2wywy = y2wy2wk = y4wk−1.
Since k − 1 is coprime to p (recall 2 ≤ k ≤ p − 2), and y4 has order 2, this generates
N = 〈y4w〉. So the Factor Group Lemma (2.1) provides a hamiltonian cycle in Cay(G;S).
For the second generating set,(
xy, y−1, y2w, y, (xy)−1, y−1, y2w, y
)
208 Ars Math. Contemp. 5 (2012) 189–215
is a hamiltonian cycle in Cay(G/N ;S) that passes through the vertices of this graph in the
order:
N,Nxy,Nx,Nxy2, Nxy3, Ny2, Ny,Ny3, N.
The endpoint of this cycle in G is
xy2wx−1ywy = xy2x−1wy2wk = y4wk−
(with  ∈ {±1} depending on whether x centralizes or inverts P .) Since k − 1 and k + 1
are coprime to p (recall 2 ≤ k ≤ p− 2) and y4 has order 2, this generates N = 〈y4w〉. So
the Factor Group Lemma (2.1) provides a hamiltonian cycle in Cay(G;S).
Subsubcase 2.3.2. Assume Q ∼= Z4 n (Z2 × Z2). Up to automorphism, any 2-
element generating set of Q is of the form {x, xiy}. Of course, by replacing x with x−1,
we may assume 0 ≤ i ≤ 2. Also, since x2y has order 2, it may be replaced with y; so we
may assume i ∈ {0, 1}.
Since Φ(Q) = 〈x2, z〉 and Q′ = 〈z〉, we must have c ∈ {x2, x2z}P . Thus, letting w
be a generator of P , either:
S = {x, y, x2w} or S = {x, xy, x2w}, or S = {x, y, x2zw}, or S = {x, xy, x2zw}.
Also:
• x acts on P by an automorphism of order 4 (so x2 inverts P ),
• y either centralizes P or inverts it, and
• z centralizes P .
Let k ∈ Zp, such that x−1wx = wk. Since the action of x on P has order 4, we have
2 ≤ k ≤ p − 2. Let N = 〈z, P 〉. Since z centralizes P , the order of z is 2, and the order
of w is p, we have N = 〈zw〉 ∼= Z2p.
For the first generating set, (
x2w, x−1, x2w, y, x−3, y
)
is a hamiltonian cycle in Cay(G/N ;S) that passes through the vertices of this graph in the
order:
N,Nx2, Nx,Nx3, Nx3y,Nx2y,Nxy,Ny,N.
Similarly, replacing each instance of x2w with x2zw yields a hamiltonian cycle in the graph
Cay(G/N ;S) for the third generating set that passes through the vertices of this graph in
the same order as the hamiltonian cycle for the first generating set. Since z is in the center
of G and z appears exactly twice in the list of edges, the endpoints of these cycles in G are
the same and they are given by
x2wxwyxy = x2wxwxz = x2wx2wkz = x4wk−1z = wk−1z.
Since k − 1 is coprime to p, and z has order 2, this generates N = 〈wz〉. So the Factor
Group Lemma (2.1) provides a hamiltonian cycle in Cay(G;S).
For the second generating set,(
x2w, x, x2w, xy, x3, (xy)−1
)
S. J. Curran, D. Witte Morris and J. Morris: Cayley graphs of order 16p are hamiltonian 209
is a hamiltonian cycle in Cay(G/N ;S) that passes through the vertices of this graph in the
order:
N,Nx2, Nx3, Nx,Nx2y,Nx3y,Ny,Nxy,N.
Similarly, replacing each instance of x2w with x2zw yields a hamiltonian cycle in the
graph Cay(G/N ;S) for the fourth generating set that passes through the vertices in the
same order as the hamiltonian cycle for the second generating set. Since z is in the center
of G and z appears exactly twice in the list of edges, the endpoints of each cycle are the
same and is given by
x2wx3wxyx3y−1x−1 = x2wx3wxyx2yz = x2wx3wx3z = x2wx2w−kz = w−(k+1)z.
Since z has order 2 and−(k+1) is coprime to p (recall 2 ≤ k ≤ p−2), this generatesN =
〈wz〉. So the Factor Group Lemma (2.1) provides a hamiltonian cycle in Cay(G;S).
7 The case where G/G′ ∼= Z2 × Z2 × Z2
Proposition 7.1. Assume |G| = 16p. If G/G′ ∼= Z2 × Z2 × Z2, then Cay(G;S) has a
hamiltonian cycle.
Proof. We proceed via case-by-case analysis.
Case 1. Assume #S = 3. Write S = {a, b, c}. Since G/G′ ∼= Z2 × Z2 × Z2, it is easy to
see that the sequence
(a, b, a, c, a, b, a, c)
is a hamiltonian cycle in Cay(G/G′;S). Also, since every nontrivial element of G/G′ has
order 2, we know s−1 ≡ s (mod G′), for every s ∈ S, so, for any choice of i1, . . . , i8 ∈
{±1},
(ai1 , bi2 , ai3 , ci4 , ai5 , bi6 , ai7 , ci8) is a hamiltonian cycle in Cay(G/G′;S). (7.1)
Now:
• If |a| = 2p, then a has order 2 in G/P , but not in G, so Corollary 2.3 and Re-
mark 2.11 apply.
• If |a| = 4p, then a2 generates G′. Since 〈a〉/G′ is normal in G/G′ ∼= (Z2)3, we
have 〈a〉 / G. Choose β, γ ∈ {±1} such that
xb = xβ and xc = xγ , for all x ∈ 〈a〉.
Then, letting ik = 1 for k /∈ {1, 3, 5}, the endpoint of the path (7.1) in G is
ai1bai3cai5bac = ai1aβi3aβγi5 g ∈ G′ = 〈a2〉, where g = bcbac.
Since each of i1, i3, i5 can be ±1 independently, the endpoints that can be obtained
in this way are:
a−3g, a−1g, ag, a3g.
Since 〈a2〉 ∼= Z2p, and at least one of any 4 consecutive integers is relatively prime
to 2p, it must be the case that at least one of these endpoints generates 〈a2〉 = G′.
So the Factor Group Lemma (2.1) applies.
210 Ars Math. Contemp. 5 (2012) 189–215
Thus, we may assume no element of S has order divisible by p. Therefore, s2 ∈ Q′ for
every s ∈ S. So we may assume
every element of S has order 2
for otherwise Corollary 2.3 and Remark 2.11 apply.
Let
g′ = abacabac = [a, b] bc [a, b] bc
be the endpoint of the path (7.1) in G.
Observation 7.2. For future reference, we note the following:
1. Since Q8 is not generated by elements of order 2, we know Q is not the group
described in (3b) of Proposition 3.3.
2. Suppose Q is the group described in (3c) of Proposition 3.3. Let S be the image of S
in Q. It is not difficult to see that xyz is the only element of order 2 that is of the
form xiyjz. Thus, we must have xyz±1 ∈ S, and the other two elements of S must
be in 〈x, y〉. Since all elements of S have order 2 (and |xy| = 4), we conclude that
S is of the form
S = {xz2i, yz2j , xyz±1 }.
Up to automorphism (replacing x with xz2i, replacing y with yz2j , and, if necessary,
replacing z with z−1), we have
S = {x, y, xyz } (if Q = Z2 n (Z2 × Z4)). (7.2)
Subcase 1.1. Assume [b, c] generatesG′. Since both b and c have order 2, they generate
a dihedral group. Since G′ = 〈(bc)2〉 has order 2p, we know 〈bc〉 has order 4p and 〈b, c〉 ∼=
D8p. Thus both b and c invert 〈bc〉 and G′.
Therefore bc centralizes G′, so g′ = [a, b]2[b, c]. So the Factor Group Lemma (2.1)
applies unless P ⊂ 〈[a, b]〉 (which implies that a inverts P ), and
[b, c] ≡ [a, b]−2 (mod Q′). (7.3)
Replacing Q by a conjugate, we may assume b ∈ Q. Write a = aw and c = cw′ with
a, c ∈ Q and w,w′ ∈ P . Since both a and c invert P , we know both a and c invert P .
We have
[b, c] = (bc)2 = (bcw′)2 = (bc)2(w′)2
and
[a, b] = (ab)2 = (awb)2 = (ab)2w−2 (since a and b invert P ),
so (7.3) tells us that
w′ = w2. (7.4)
Subsubcase 1.1.1. Assume [a, b] generates G′. We may interchange a and c, so the
preceding calculations tell us that w = (w′)2 = (w2)2 = w4. Therefore, we must have
p = 3.
Subsubsubcase 1.1.1.1. AssumeQ is as described in Proposition 3.3(3c). From
(7.2) and (7.4), we see that
S = {xw, y, xyzw−1}, where P = 〈w〉.
S. J. Curran, D. Witte Morris and J. Morris: Cayley graphs of order 16p are hamiltonian 211
Let N = 〈xy〉 = {e, xy, z2, xyz2} be the cyclic group of order 4 generated by xy.
Observe that N /G and that the graph Cay(G/N ;S) is isomorphic to Cay(D12; {R,F}),
where {R,F} is the natural generating set for D12, under the vertex identification φ :
G/N → D12 given by
φ(N(xwy)k) = R2k,
φ(N(xwy)k(xw)) = R2k+1,
φ(N(xwy)k(xyzw−1)) = R2kF, and
φ(N(xwy)k(xw)(xyzw−1)) = R2k+1F,
for any integer k. The natural hamiltonian cycle (R5, F )2 in Cay(D12; {R,F}) corre-
sponds to the hamiltonian cycle
((xw, y)3#, xyzw−1, (y, xw)3#, xyzw−1)
in Cay(G/N ;S). The endpoint in G is
(xwy)3(y−1)(xyzw−1)(yxw)3(xw)−1(xyzw−1) =
= (xyz2)(y)(xyzw−1)(xy)(w−1x)(xyzw−1)
= (xyz2)(xz−1w−1)(xy)(yzw)
= (yz−1w−1)(xzw) = xyz2 = (xy)−1,
which generates 〈xy〉 = N . Thus, the Factor Group Lemma (2.1) provides a hamiltonian
cycle in Cay(G;S).
Subsubsubcase 1.1.1.2. Assume Q = D8 × Z2 = 〈f, t〉 × Z2. Since [a, b] is
nontrivial, we may assume a = f and b = ft. Because 〈b, c〉 is a dihedral group and S is
minimal, we must have c = ftiz, for some integer i. Since [b, c] = (bc)2 = (ftftiz)2 =
t2i−2 is nontrivial, i must be even. We may replace z with t2z since the order of t2z is 2
and t2z ∈ Z(Q). Thus we may assume c = fz. Then, from (7.4), we see that
S = {fw, ft, fzw−1},
where f inverts w, whereas t and z centralize w (and w is a generator of P ).
LetN = 〈tz〉 = {e, tz, t2, t3z} be the cyclic group of order 4 generated by tz. Observe
thatN/G and that Cay(G/N ;S) is graph isomorphic to Cay(D12; {R,F}), where {R,F}
is the natural generating set for D12, under the vertex identification φ : G/N → D12 given
by
φ(N((ft)(fzw−1))k) = R2k,
φ(N((ft)(fzw−1))k(ft)) = R2k+1,
φ(N((ft)(fzw−1))k(fw)) = R2kF, and
φ(N((ft)(fzw−1))k(ft)(fw)) = R2k+1F,
for any integer k. The natural hamiltonian cycle (R5, F )2 in Cay(D12; {R,F}) corre-
sponds to the hamiltonian cycle
((ft, fzw−1)3#, fw, (fzw−1, ft)3#, fw)
212 Ars Math. Contemp. 5 (2012) 189–215
in Cay(G/N ;S). The endpoint in G is
(ftfzw−1)3(fzw−1)−1(fw)(fzw−1ft)3(ft)−1(fw) =
= (tz)(wz−1f−1)(fw)(t3z)(t−1f−1)(fw)
= (tz)(wz−1w)(t3z)(t−1w)
= (tw2)(t2zw) = t3z = (tz)−1,
which generates 〈tz〉 = N . Thus, the Factor Group Lemma (2.1) provides a hamiltonian
cycle in Cay(G;S).
Subsubcase 1.1.2. Assume [a, b] does not generate G′. Because we could inter-
change b and c, we may assume [a, c] also does not generate G′. Since
[a, c] = (ac)2 = (aw cw2)2 = (a cw)2 = (a c)2w2,
and w2 generates P , this implies that a commutes with c. By the same argument, a com-
mutes with b. So a is in the center of Q. Therefore Q = 〈b, c〉 × 〈a〉. Looking at the list of
groups in Proposition 3.3(3) (and recalling that a, b, and c all have order 2), we conclude
that Q = D8 × Z2. Furthermore, we have a = z, and 〈b, c〉 = D8, so we may assume
S = {zw, f, ftw2}
where f and z invert w, and t centralizes w (and w is the generator of P ).
Let N = Q′ = 〈t2〉 = {e, t2}. Observe that the graph Cay(G/N ;S) is isomorphic to
Cay(Z2nZ4p; {X,Y }), where {X,Y } is the natural generating set for Z2nZ4p given by
Z2 n Z4p = 〈X,Y |X2 = Y 4p = 1, X−1Y X = Y 2p−1〉.
This graph isomorphism is given by the vertex identification φ : G/N → Z2 n Z4p where
φ(N(fftw2)k) = Y 2k,
φ(N(fftw2)kf) = Y 2k+1,
φ(N(fftw2)k(zw)) = Y 2kX, and
φ(N(fftw2)k(f)(zw)) = Y 2k+1X,
for any integer k. The hamiltonian cycle (Y 2p−1, X)4 in Cay(Z2 n Z4p; {X,Y }) corre-
sponds to the hamiltonian cycle
((f, ftw2)p#, zw, (ftw2, f)p#, zw)2
in Cay(G/N ;S). The endpoint in G is(
(fftw2)p(ftw2)−1(zw)(ftw2f)p(f)−1(zw)
)2
=
=
(
(tp)(w−2t−1f−1)(zw)(t−p)(f−1)(zw)
)2
=
(
(ft−p+1w2)(zw)(ftp)(zw)
)2
= (t2p−1)2 = t2,
S. J. Curran, D. Witte Morris and J. Morris: Cayley graphs of order 16p are hamiltonian 213
which generates 〈t2〉 = N . Thus, the Factor Group Lemma (2.1) provides a hamiltonian
cycle in Cay(G;S).
Subcase 1.2. Assume there do not exist s, t ∈ S, such that 〈[s, t]〉 = G′. Then, since
〈[a, b], [a, c], [b, c]〉 = G′ = Q′ × P,
we may assume 〈[a, b]〉 = P and 〈[b, c]〉 = Q′.
Note that if bc centralizes G′, then g′ = [a, b]2[b, c], so g′ generates G′. Therefore,
the Factor Group Lemma (2.1) applies in this case. Thus, we may assume bc does not
centralize G′, so
bc inverts G′.
Subsubcase 1.2.1. Assume Q = D8 × Z2. Since 〈b, c〉 is dihedral and Q′ =
〈[b, c]〉 = 〈(bc)2〉 has order 2, it must be the case that ab has order 4 and 〈b, c〉 ∼= D8. So
we may assume b = f and c = ft.
Write a = aw with a ∈ Q and w ∈ P . Since a and b have order 2, we know they
generate a dihedral group, so a and b both invert P , but c centralizes P (since bc invertsG′).
Since [a, b] ∈ P projects trivially into Q, we know a commutes with b = f , so a ∈
〈f, t2〉z. However, since t2z is in the center of Q, there is no harm in replacing z with t2z,
so we may assume a ∈ 〈f〉z. Thus, there are only two generating sets to consider:
S = {zw, f, ft} or S = {fzw, f, ft} .
In each case, assume the first two generators invert P , and the third generator central-
izes P . (Thus, in both cases, f and t invert P . However, z inverts P in the first case, but
z centralizes P in the second case.)
The cycle
(
(ft, f)4#, a
)2
in each of these generating sets (so in the first, a = zw, and
in the second, a = fzw) is a hamiltonian cycle in Cay(G/P ;S), and its endpoint in G is(
(ftf)4f−1a
)2
= (fa)2. In the first case, the endpoint (fa)2 is (fzw)2 = f2z2w2 = w2,
while in the second case, it is (ffzw)2 = (zw)2 = w2. Since w2 certainly generates P ,
the Factor Group Lemma (2.1) provides a hamiltonian cycle in Cay(G;S).
Subsubcase 1.2.2. AssumeQ 6= D8×Z2. We will show that this case cannot occur.
From (7.2), it is easy to see that no two elements of S commute. So the image of [a, b] in Q
is nontrivial, which contradicts the fact that 〈[a, b]〉 = P .
Case 2. Assume #S > 3. Since G/P ∼= Q is a 3-generated 2-group, there is a 3-element
subset {a, b, c} of S that generates G/P . The minimality of S implies 〈a, b, c〉 6= G, so
|〈a, b, c〉| = 16. Thus, we may assume 〈a, b, c〉 = Q.
Since a, b, and c all have order 2 in Q/Q′, they also have order 2 in G/Q′. So we may
assume
a, b, and c all have order 2
for otherwise Corollary 2.3 and Remark 2.11 apply.
Let s be the fourth element of S. We may assume s /∈ G′, for otherwise Lemma 2.10
and Remark 2.11 apply with X = {s}.
Let s = wq where w generates P and q ∈ Q. If c centralizes P , we have
[c, s] = c−1(wq)−1cwq = (q−1)c(w−1)cwq = (q−1)cw−1wq = (q−1)cq = [c, q] ∈ Q′.
214 Ars Math. Contemp. 5 (2012) 189–215
Since
G′ = Q′ × P = 〈[a, b], [a, c], [b, c], [a, s], [b, s], [c, s]〉
and Q′ = 〈[a, b], [a, c], [b, c]〉, we may assume P ⊂ 〈[c, s]〉. Thus [c, s] 6∈ Q′ and c inverts
P . Therefore, P ⊂ 〈[c, s]〉 ⊂ 〈c, s〉.
We claim that s ∈ cG′. If not, then the image of 〈c, s〉 in G/G′ has order 4, so we
may assume {a, c, s} generates G/G′ ∼= Q/Q′ = Q/Φ(Q). But this implies that {a, c, s}
generates G/P ∼= Q. Since we also know that P ⊂ 〈c, s〉 ⊂ 〈a, c, s〉, we conclude that
〈a, c, s〉 = G. This contradicts the minimality of S.
We may assume s /∈ cP , for otherwise Corollary 2.2 and Remark 2.11 apply. Let u be
a generator of Q′ ∼= Z2. Then s ∈ cG′ = cQ′P = {c, cu}P . Since s 6∈ c P and s 6∈ Q,
we have s = cuw for some generator w of P ∼= Zp. Let γ = uw. Then s = cγ and
〈γ〉 = 〈uw〉 = 〈u〉〈w〉 = Q′P = G′.
Since [c, s] generates P , we see that c inverts P .
We claim that both a and b centralize P . If not, we may assume a inverts P . Then
P ⊂ 〈[a, s]〉 ⊂ 〈a, s〉. Since {a, b, s} and {a, b, c} have the same image in G/G′ ∼=
Q/Q′ = Q/Φ(Q), we know {a, b, s} generatesG/G′. This implies that {a, b, s} generates
G/P ∼= Q. Hence, {a, b, s} generates G, contradicting the minimality of S.
Now, sinceG/G′ ∼= Z2×Z2×Z2 (and s ≡ c (mod G′)), it is easy to see that all three
of the following sequences are hamiltonian cycles in Cay(G/G′;S):
(a, c, b, c, a, c, b, c), (a, c, b, c, a, c, b, s), (a, c, b, s, a, c, b, s).
Let g = acbcacbc be the endpoint (in G) of the first cycle. Then the endpoints of the other
two cycles are:
gc−1s = g γ and acbsacbs = acb(cγ)acb(cγ) = g γ2.
Now g ∈ Q′ = 〈γp〉, and |γ| = 2p. Now, it is easy to see that if m is a multiple of p, then
either m + 1 or m + 2 is relatively prime to 2p. Therefore, either g γ or g γ2 generates
〈γ〉 = G′, so the Factor Group Lemma (2.1) applies.
References
[1] B. Alspach, Lifting Hamilton cycles of quotient graphs, Discrete Math. 78 (1989), 25–36.
[2] W. Burnside, Theory of Groups of Finite Order, 2nd ed. Dover, New York, 1955.
[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–34.
[4] S. J. Curran, D. W. Morris and J. Morris Cayley graphs of order 48 are hamiltonian (unpub-
lished). http://arxiv.org/src/1104.0081/anc/48.pdf
[5] E. Ghaderpour and D. W. Morris, Cayley graphs of order 27p are hamiltonian, Int. J. Comb.
2011 (2011), Article ID 206930, 16 pages.
[6] E. Ghaderpour and D. W. Morris, Cayley graphs of order 30p are hamiltonian (preprint).
http://arxiv.org/abs/1102.5156
[7] D. Gorenstein, Finite Groups, Chelsea, New York, 1980.
S. J. Curran, D. Witte Morris and J. Morris: Cayley graphs of order 16p are hamiltonian 215
[8] T. W. Judson, Abstract Algebra, Virginia Commonwealth University, 2009.
http://abstract.pugetsound.edu/download.html
[9] K. Keating and D. Witte On Hamilton cycles in Cayley graphs with cyclic commutator sub-
group, Ann. Discrete Math. 27 (1985), 89–102.
[10] K. Kutnar, D. Marušič, J. Morris, D. W. Morris and P. Šparl, Hamiltonian cycles in Cayley
graphs whose order has few prime factors, Ars Math. Contemp. 5 (2012), 27–71.
[11] D. W. Morris, 2-generated Cayley digraphs on nilpotent groups have hamiltonian paths, Con-
trib. Discrete Math. (to appear). http://arxiv.org/abs/1103.5293
[12] D. Witte: Cayley digraphs of prime-power order are hamiltonian. J. Comb. Theory B 40 (1986),
107–112.
[13] D. Witte and J. A. Gallian, A survey: Hamiltonian cycles in Cayley graphs, Discrete Math. 51
(1984), 293–304.