ISSN 2148-838Xhttp://dx.doi.org/10.13069/jacodesmath.66457
J. Algebra Comb. Discrete Appl.
3(1) • 13–30
Received: 17 July 2015
Accepted: 24 November 2015
Journal of Algebra Combinatorics Discrete Structures and Applications
Infinitely many nonsolvable groups whose Cayley
graphs are hamiltonian
Research Article
Dave Witte Morris
Abstract: We show there are infinitely many finite groups G, such that every connected Cayley graph on G has
a hamiltonian cycle, and G is not solvable. Specifically, we show that if A5 is the alternating group
on five letters, and p is any prime, such that p ≡ 1 (mod 30), then every connected Cayley graph on
the direct product A5 × Zp has a hamiltonian cycle.
2010 MSC: 05C25, 05C45
Keywords: Cayley graph, Hamiltonian cycle, Solvable group, Alternating group
1. Introduction
It has been conjectured that every connected Cayley graph on every finite group has a hamiltonian
cycle (unless the graph has less than three vertices). In support of this conjecture, the literature provides
numerous infinite families of finite groups G, for which it is known that every connected Cayley graph
on G has a hamiltonian cycle. (See [2] and its references for more information.) However, it seems that
the union of these families contains only finitely many groups that are not solvable. This note puts an
end to that unsatisfactory state of affairs:
Proposition 1.1. There are infinitely many finite groups G, such that every connected Cayley graph
on G has a hamiltonian cycle, and G is not solvable.
Since the alternating group A5 (of order 60) is a nonabelian simple group, and is therefore not
solvable, the above is an immediate consequence of the following more specific result.
Proposition 1.2. If p is a prime, such that p ≡ 1 (mod 30), then every connected Cayley graph on the
direct product A5 ×Zp has a hamiltonian cycle.
Dave Witte Morris; Department of Mathematics and Computer Science, University of Lethbridge, Canada (email:
Dave.Morris@uleth.ca).
13
D. W. Morris / J. Algebra Comb. Discrete Appl. 3(1) (2016) 13–30
The proof is based on a case-by-case analysis of Cayley graphs of the group A5. Most of the
hamiltonian cycles were found by computer search (using a fairly naive backtracking algorithm).
Remark 1.3. Rather than merely groups that are not solvable, it would be much more interesting to find
infinitely many finite, simple groups G, such that every connected Cayley graph on G has a hamiltonian
cycle. Regrettably, the known methods seem to be hopelessly inadequate for this problem.
2. Preliminaries
Definition 2.1. Let S be a subset of a finite group G. The Cayley graph of G with respect to the
connection set S is the graph Cay(G; S) whose vertices are the elements of G, and with edges g gs and
g gs−1, for each g ∈ G and s ∈ S.
Notation 2.2. Suppose S is a subset of a finite group G. For s1, . . . ,sm ∈ S ∪S−1, we use (si)mi=1 =
(s1, . . . ,sm) to denote the walk in Cay(G; S) that visits (in order), the vertices
e, s1, s1s2, s1s2s3, . . . , s1s2 · · ·sm.
We use (s1, . . . ,sm)k to denote the concatenation of k copies of the sequence (si)mi=1, and the following
illustrates other notations that are often useful:
(a2,b−3,si)
3
i=1 = (a,a,b
−1,b−1,b−1,s1,a,a,b
−1,b−1,b−1,s2,a,a,b
−1,b−1,b−1,s3).
Notation 2.3. We use : A5 ×Zp → A5 to denote the natural projection (so (x,y) = x).
Our argument in Section 3 is based on the same outline as the proof in [3] of the following result.
Lemma 2.4 ([3]). Every connected Cayley graph on A5 has a hamiltonian cycle.
The following result is the reason that the statement of Proposition 1.2 assumes p ≡ 1 (mod 30). A
much weaker hypothesis would suffice in all other parts of the proof.
Corollary 2.5. Let S be a minimal generating set of A5 × Zp, where p is prime, and p ≡ 1 (mod 30).
If there exists a ∈ S, such that S r{a} generates A5, then Cay(A5 ×Zp; S) has a hamiltonian cycle.
Proof. Since gcd(|A5|,p) = 1, the minimality of S implies that 〈S r {a}〉 = A5. (Namely, since
gcd(|A5|,p) = 1, we have g ∈ 〈g〉 for every g ∈ A5 × Zp. Therefore A5 = 〈S r{a}〉 ⊆ 〈S r {a}〉. Since
the minimality of S implies a /∈ 〈S r {a}〉, we conclude that 〈S r {a}〉 = A5.) From Lemma 2.4, we
know there is a hamiltonian cycle (si)60i=1 in Cay(A5; S r {a}). Since, by assumption, p − 1 is divisible
by 30 = 2 · 3 · 5 (and every element of A5 has order 1, 2, 3, or 5), we know a p−1 is trivial. This means
ap−1 ∈ Zp (so ap−1 centralizes A5), so it is not difficult to verify that(
s2i−1,a
p−1,s2i,a
−(p−1))30
i=1
is a hamiltonian cycle in Cay(A5 ×Zp; S).
For completeness, we sketch the verification that the given walk is a hamiltonian cycle. Since
〈S〉 = A5 × Zp, and S r {a} ⊆ A5, we know that a projects nontrivially to Zp. Since gcd(|A5|,p) = 1,
this implies Zp ⊆ 〈a〉, so every element g of A5 × Zp can be written (uniquely) in the form g = xar
with x ∈ A5 and 0 ≤ r ≤ p− 1. Since (si)60i=1 is a hamiltonian cycle in a Cayley graph on A5, we have
x = s1s2 · · ·sk, for some k with 0 ≤ k < 60. If k = 2i− 1 is odd, then
g = xar =
i−1∏
j=1
s2j−1s2j
s2i−1ar =
i−1∏
j=1
(s2j−1a
p−1s2ja
−(p−1)
s2i−1ar.
14
D. W. Morris / J. Algebra Comb. Discrete Appl. 3(1) (2016) 13–30
(because ap−1 ∈ Zp is in the center of A5 ×Zp). Also, if k = 2i is even, then
g = xar =
i−1∏
j=1
s2j−1s2j
s2i−1s2iar =
i−1∏
j=1
s2j−1a
p−1s2ja
−(p−1)
s2i−1ap−1s2ia−(p−1−r).
Thus, we see (in either case) that g is one of the vertices on the walk (s2i−1,ap−1,s2i,a−(p−1))30i=1. This
means that the walk passes through all of the vertices in Cay(A5 ×Zp; S).
Also, note that the walk has the correct length (60p) to be a hamiltonian cycle. Finally, by using
once again the fact that ap−1 is in the center, we see that the terminal vertex of the walk is
30∏
i=1
s2i−1a
p−1s2ia
−(p−1) =
30∏
i=1
s2i−1s2i =
60∏
i=1
si = e,
because (si)60i=1 is a (hamiltonian) cycle.
Remark 2.6. For definiteness, we point out that we write our permutations on the left, so gs(i) = g
(
s(i))
for g,s ∈ A5 and i ∈{1, 2, 3, 4, 5}.
The remainder of this section records a few easy consequences of the following well-known, elementary
observation.
Lemma 2.7 (“Factor Group Lemma” [4, §2.2]). Suppose
• N is a cyclic, normal subgroup of G,
• (si)mi=1 is a hamiltonian cycle in Cay(G/N; S), and
• the voltage Π(si)mi=1 generates N.
Then (s1,s2, . . . ,sm)|N| is a hamiltonian cycle in Cay(G; S).
Corollary 2.8 ([2, Cor. 2.11]). Suppose
• N is a normal subgroup of G, such that |N| is prime,
• the image of S in G/N is a minimal generating set of G/N,
• there is a hamiltonian cycle in Cay(G/N; S), and
• s ≡ t (mod N) for some s,t ∈ S ∪S−1 with s 6= t.
Then there is a hamiltonian cycle in Cay(G; S).
Corollary 2.9. Let S be a minimal generating set of A5 × Zp, such that S is a minimal generating set
of A5. If every element of S has order 2, then Cay(A5 ×Zp; S) has a hamiltonian cycle.
Notation 2.10. Let C = (si)mi=1 be a walk in a Cayley graph Cay(G; S). For s ∈ S, we use wtC (s) to
denote the difference between the number of occurrences of s and the number of occurrences of s−1 in C.
(This is the net weight of the generator s in C.)
Lemma 2.11. Let S = {a1, . . . ,ak,b1, . . . ,b`} be a minimal generating set of A5 × Zp, such that S is a
minimal generating set of A5. Assume
• ` ≥ 1, and |ai| = 2 for all i,
• C1, . . . ,C` are hamiltonian cycles in Cay(A5; S), and
15
D. W. Morris / J. Algebra Comb. Discrete Appl. 3(1) (2016) 13–30
• [wtCi (bj)] is the `× ` matrix whose (i,j) entry is wtCi (bj).
If det[wtCi (bj)] 6≡ 0 (mod p), then Cay(A5 ×Zp; S) has a hamiltonian cycle.
Proof. We may assume that ai ∈ A5 for 1 ≤ i ≤ k, for otherwise Corollary 2.8 applies with s = ai and
t = a−1i . Write bi = (bi,vi) (with vi ∈ Zp) for 1 ≤ i ≤ `. Since S generates A5×Zp, the vector [v1, . . . ,v`]
must be nonzero in (Zp)`. Then, since, by assumption, the matrix [wtCi (bj)] is invertible over Zp, this
implies [wtCi (bj)][v1, . . . ,v`]
T 6= ~0 in (Zp)`, so there is some i, such that
∑`
j=1 wtCi (bj) vj 6= 0 in Zp.
We now show that this sum is precisely the voltage ΠCi of the walk Ci, so Lemma 2.7 provides
the desired hamiltonian cycle in Cay(A5 × Zp; S). Write Ci = (sk)nk=1, let π =
∏n
k=1 sk be the voltage
of Ci, and let n(s) and n′(s), respectively, be the number of occurrences of s and s−1 in Ci. Since Ci is a
(hamiltonian) cycle in Cay(A5; S), we know that π is trivial, so π =
∑n
k=1 s
∗
k, where s
∗
k is the projection
of sk to Zp. Noting that (s−1)∗ = −s∗ for s ∈ S, we have
π =
n∑
k=1
s∗k =
∑
s∈S∪S−1
n(s)s∗ =
∑
s∈S
(
n(s) −n′(s)
)
s∗ =
∑
s∈S
wtCi (s) s
∗ =
∑̀
j=1
wtCi (bj) vj.
3. Proof of Proposition 1.2
Assumptions 3.1. Let S be a minimal generating set of A5 × Zp (and, in accordance with Notation
2.3, let S be the image of S in A5). We may assume S is a minimal generating set of A5, for otherwise
Corollary 2.5 applies. We may also assume, for every element s of S with |s| = 2, that the projection
of s to Zp is trivial, for otherwise Corollary 2.8 applies.
Case 1. Assume S has exactly two elements. Write S = {a,b}.
Subcase 1.1. Assume |a| = 2 and |b| = 3. To simplify matters, we show that, by applying
an automorphism of A5, we may assume a = (1, 2)(3, 4) and b = (2, 4, 5). First of all, we may assume
a = (1, 2)(3, 4), since every element of order 2 in A5 is conjugate to this. Then, in order for 〈a,b〉 to be
transitive, the support of b must contain an element of each cycle of a (including the 1-cycle (5)). So we
may assume b = (2, 4, 5) (after conjugating by (1, 2) and/or (3, 4), if necessary).
Now, we have the following hamiltonian cycle in Cay(A5; S) (see note 4.1):
C1 =
(
(a,b 2)3, (a,b−2)3, (a,b 2,a,b−2)2
)2
.
By using the fact that each left coset of 〈b〉 appears as consecutive vertices in this cycle, we will show
that
C2 =
(
(a,b3p−1)3, (a,b−(3p−1))3, (a,b3p−1,a,b−(3p−1))2
)2
passes through all of the vertices in each left coset of 〈b〉, and is therefore a hamiltonian cycle in Cay(A5×
Zp; S).
Note that b3p−1 = b2 (since |b| = 3). This implies that if we let x be the terminal vertex of the
walk C2, then x is the terminal vertex of the hamiltonian cycle C1, so x is trivial. The projection of x
to Zp is also trivial, because wtC2 (b) = 0. Therefore, the walk C2 is closed.
Now, since C2 has the correct length to be a hamiltonian cycle, we need only show that it passes
through every element of A5 × Zp. From the fact that b3p−1 = b2, we see that the vertices of C2 are
precisely the same elements of A5 as the vertices of C1; that is, the walk C2 passes through every element
of A5. Thus, given any v ∈ A5 × Zp, the walk C2 visits some vertex w with w = v; that is, v and w are
in the same coset of Zp. Since Zp ⊆〈b〉, this implies that v and w are in the same left coset of 〈b〉. Also,
16
D. W. Morris / J. Algebra Comb. Discrete Appl. 3(1) (2016) 13–30
since there are never two consecutive appearances of a in C2, and every occurrence of b is contained in a
string b3p−1, we know that C2 traverses every element of any left coset of 〈b〉 that it enters. In particular,
C2 traverses every element of the left coset of w, so it passes through v.
Subcase 1.2. Assume |a| = 2 and |b| = 5. We may assume b = (1, 2, 3, 4, 5), after conjugating
by some permutation in S5. Since |a| = 2, it has a fixed point, which we may assume is 5 (after conjugating
by a power of b). So |a| must be either (1, 2)(3, 4), (1, 3)(2, 4), or (1, 4)(2, 3).
• For a = (1, 2)(3, 4), we have the following hamiltonian cycle (see note 4.2):
C =
(
(a,b,a,b 4)2,a,b 2,a,b−1,a,b 4,a,b, (a,b 2)3,
a,b−2,a,b 4,a,b−2, (a,b)2,a,b−1,a,b 4,a,b 2
)
.
Since wtC (b) = 29 6≡ 0 (mod p), Theorem 2.11 applies.
• For a = (1, 3)(2, 4), we have the following hamiltonian cycle (see note 4.3):
C =
(
a,b 4,a,b−1,a,b,a,b−1,a,b−4,a,b−2, (a,b−4,a,b 2)2,
a,b−4,a,b,a,b−1,a,b−4,a,b−2,a,b−4,a,b 2
)
.
Since wtC (b) = −19 6≡ 0 (mod p), Theorem 2.11 applies.
• If a = (1, 4)(2, 3), then a normalizes b, so 〈a,b〉 6= A5, which contradicts the fact that S is a
generating set.
Subcase 1.3. Assume |a| = |b| = 3. The union of the supports of a and b must be all of
{1, 2, 3, 4, 5}, since 〈a,b〉 is transitive. Since each support consists of three elements, the intersection
must be a single element, which we may assume is 3. Then, by renumbering, we may assume the support
of a is {1, 2, 3} and the support of b is {3, 4, 5}. Therefore, either a or a−1 is (1, 2, 3), and either b or b−1
is (3, 4, 5). So we may assume a = (1, 2, 3) and b = (3, 4, 5). We have the following hamiltonian cycle (see
note 4.4):
C1 =
(
b,a,b 2,a 2,b−2,a−2,b 2,a 2,b 2,a−2,b−2,a−2,b 2,a 2,b−2,a,b−2,
a−2,b 2,a,b,a−1,b−2,a 2,b 2,a 2,b−2,a−2,b−1,a,b,a 2,b−1,a−2,b−1,a
)
.
Note that wtC1 (a) = 4 and wtC1 (b) = 0. Conjugation by the permutation (1, 4)(2, 5) interchanges a and b,
and therefore yields a hamiltonian cycle C2 with wtC2 (a) = 0 and wtC2 (b) = 4. Since det [
4 0
0 4 ] = 16 6≡ 0
(mod p), Theorem 2.11 applies.
Subcase 1.4. Assume |a| = 3 and |b| = 5. We may assume b = (1, 2, 3, 4, 5), by replacing it
with a conjugate. Then the two fixed points of the 3-cycle a are either consecutive or are separated by
only one element (in circular order). Therefore, after conjugating by a power of b, we may assume that
one of the fixed points of a is 5, and the other is either 3 or 4. Hence, a is either (1, 2, 4) or (1, 2, 3) (or
the inverse of one of these).
• If a = (1, 2, 4), then we have the following two hamiltonian cycles (see notes 4.5 and 4.6):
C1 =
(
a 2,b−2,a−2,b−1,a−1,b,a 2,b−1,a−2,b,a−2,b−2,a−2,b−1,a−1,b,a 2,b−1,a 2,b,
a−2,b−1,a 2,b,a 2,b−1,a−2,b,a−2,b−2,a−2,b−1,a−1,b,a 2,b−1, (a−2,b)2
)
and
C2 =
(
a 2,b−2,a−2,b−1,a−1,b, (a 2,b−1)2,a 2,b−2,a−2,b−1,a−1,b,a 2,b−1,a 2,b,
a−2,b−1,a 2,b,a 2,b−1,a−2,b,a−2,b−2,a−2,b−1,a−1,b,a 2,b−1, (a−2,b)2
)
Then
[
wtC1 (a), wtC1 (b)
]
= [−9,−5] and
[
wtC2 (a), wtC2 (b)
]
= [−1,−7]. Since det
[−9 −5
−1 −7
]
= 58 6≡ 0
(mod p), Theorem 2.11 applies.
17
D. W. Morris / J. Algebra Comb. Discrete Appl. 3(1) (2016) 13–30
• If a = (1, 2, 3), then we have the following two hamiltonian cycles (see notes 4.7 and 4.8):
C1 =
(
a 2,b−2,a−2,b−1,a−1,b 3, (a 2,b)2,a,b−1, (a 2,b)2,a 2,b−2,a 2,b,a,b−1,
a−2,b,a 2,b−1,a−2,b,a−1,b−2,a−1,b−1,a−2,b,a 2, (b−1,a−2)2,b
)
and
C2 =
(
a 2,b−1, (a 2,b)2,a 2,b−1,a−2,b,a−2,b−1,a 2,b,a 2,b−1,a−2,b 2,
(a−2,b−1)2, (a−2,b)2,a 2,b,a 2,b−1,a,b,a−2,b,a 2, (b−1,a−2)2,b
)
Then
[
wtC1 (a), wtC1 (b)
]
= [5,−1] and
[
wtC2 (a), wtC2 (b)
]
= [−1, 3]. Since det
[
5 −1
−1 3
]
= 14 6≡ 0
(mod p), Theorem 2.11 applies.
Subcase 1.5. Assume |a| = |b| = 5. By applying an automorphism of A5, we may assume
a = (1, 2, 3, 4, 5). From Sylow’s Theorems, we know that A5 has precisely six Sylow 5-subgroups. One of
them is 〈a〉, and 〈a〉 acts transitively on the other 5 by conjugation. So we may assume, after conjugating
by a power of a, that 〈b〉 = 〈(1, 2, 3, 5, 4)〉. Then, by replacing b with its inverse if necessary, we may
assume b is either (1, 2, 3, 5, 4) or (1, 3, 4, 2, 5).
• If b = (1, 2, 3, 5, 4), then we have the following hamiltonian cycle (see note 4.9):
C1 =
(
b,a−1,b,a,b 4,a,b 2,a−1,b 2,a−1,b−1,a−1,b,a−1,b,a,b 2,a−1,b 2,a−1,b−1,
a,b−2,a−1,b−4,a−1,b−1,a,b−4,a,b−2,a−1,b−1,a,b−2,a−1,b 4,a,b−2,a
)
,
Then
[
wtC1 (a), wtC1 (b)
]
= [−2, 0]. Conjugating by the permutation (4, 5) interchanges a and b, and
therefore yields a hamiltonian cycle C2 with
[
wtC2 (a), wtC2 (b)
]
= [0,−2]. Since det
[−2 0
0 −2
]
= 4 6≡ 0
(mod p), Theorem 2.11 applies.
• If b = (1, 3, 4, 2, 5), then we have the following two hamiltonian cycles (see notes 4.10 and 4.11):
C1 =
(
a 4,b−1,a−4,b,a 4,b−1,a 2,b,a−2,b,a−1,b,a−4,b−1,
a−1,b−1,a 4,b, (a−4,b−1)2, (a 2,b)2,a 4, (b−1,a)2,b
)
and
C2 =
(
a 4,b−1,a−4,b,a 4,b−1,a 2,b,a−1,b−1,a−4,b−1,a,b−1,
a−2,b−1,a 4,b, (a−4,b−1)2, (a 2,b)2,a 4, (b−1,a)2,b
)
Then
[
wtC1 (a), wtC1 (b)
]
= [4, 0] and
[
wtC2 (a), wtC2 (b)
]
= [6,−4]. Since det
[
4 0
6 −4
]
= −16 6≡ 0
(mod p), Theorem 2.11 applies.
Case 2. Assume S has at least three elements.. We claim that S has exactly three elements, so we may
write S = {a,b,c} with |a| ≤ |b| ≤ |c|. To show this, write S = {s1, . . . ,sr}, and suppose r ≥ 4. Let
Hi = 〈s1, . . . ,si〉 for each i, and note that, since S is a minimal generating set, we have Hi−1 ( Hi.
Since |A5| = 22 · 3 · 5 is the product of only 4 primes, we must have r = 4 and |Hi : Hi−1| is prime
for i = 1, . . . , 4. Since A4 is the only subgroup of prime index in A5 (up to conjugacy), we may assume
H3 = A4. Then H2 must be the Sylow 2-subgroup of A4, since that is the only subgroup of prime index.
So H3 = A4 is generated by s1 and s3, contradicting the minimality of S.
Subcase 2.1. Assume |c| = 5. Since a and b cannot both normalize 〈c〉 (but every proper
subgroup of A5 whose order is divisible by 5 has order 5 or 10), we see that either 〈a,c〉 = A5 or
〈b,c〉 = A5, which contradicts the minimality of S.
Subcase 2.2. Assume |a| = |b| = |c| = 3. The minimality of S implies that 〈a,b〉 6= A5, so
there must be at least two elements in the intersection of the supports of a and b. The supports cannot
18
D. W. Morris / J. Algebra Comb. Discrete Appl. 3(1) (2016) 13–30
be equal, since a 6= b±1. Therefore, the intersection of the supports consists of two points, which we
may assume are 1 and 5. Then we may assume a = (1, 2, 5) and b = (1, 3, 5). Now, for the same reason,
the support of c must contain exactly two points from the support of a and exactly two points from the
support of b, and it must also contain 4 (since 4 is fixed by both a and b, but not by A5). This implies
that the support of c is {1, 4, 5}, so c = (1, 4, 5)±1. Therefore (perhaps after replacing c by its inverse),
we have
S = {(1, 2, 5), (1, 3, 5), (1, 4, 5)} = {(1,j,n) | 1 < j < n} for n = 5.
So [1, App. D] provides the following hamiltonian cycle in Cay(A5; S) (see note 4.12):
R1 =
((
(a 2,b)2,a 2,c
)2
,a,b, (b,a 2)2,c 2,a 2,c,b,a,b,c,a, (c,b 2)2, (a 2,b)2,a,c 2,a,b 2, (a,c 2)2
)
.
We have [wtR1 (a), wtR1 (b), wtR1 (c)] = [29, 17, 14]. Conjugating by (2, 3, 4) and (2, 3, 4)
2 cyclically per-
mutes {a,b,c}, and therefore yields hamiltonian cycles R2 and R3, such that
[wtR2 (a), wtR2 (b), wtR2 (c)] = [17, 14, 29] and [wtR3 (a), wtR3 (b), wtR3 (c)] = [14, 29, 17].
Since
det
29 17 1417 14 29
14 29 17
= 11, 340 = 22 · 34 · 5 · 7 6≡ 0 (mod p),
Theorem 2.11 applies.
Subcase 2.3. Assume |a| = 2 and |b| = |c| = 3. We claim that we may assume S =
{(12)(45), (1, 2, 3), (1, 2, 4)}. Arguing as in the first paragraph of Subcase 2.2 (and renumbering), we may
assume b = (1, 2, 3) and c = (1, 2, 4). Since 〈a,b,c〉 = A5 is transitive on {1, 2, 3, 4, 5}, we know that 5 is
in the support of a. Also, since 〈a,b〉 6= A5, we know that the support of b does not contain precisely one
element of each of the cycles of a (and similarly for the support of c).
If one of the cycles of a is disjoint from the support of b, then the cycle must be (4, 5). The support
of c contains precisely one element of this cycle, and cannot be disjoint from the other cycle, so it must
contain the entire cycle. The only 2-element subset of {1, 2, 3} contained in the support of c is {1, 2}, so
a = (1, 2)(4, 5), as desired.
We may now assume that no cycle of a is disjoint from the support of b or the support of c. (This
will lead to a contradiction.) This assumption implies that the cycle (x, 5) in a must be either (1, 5) or
(2, 5). We may assume it is (1, 5) (after conjugating by (1, 2) and replacing b and c by their inverses, if
necessary). The other cycle either is (2, 3) (in which case, 〈a,c〉 = A5), or is either (2, 4) or (3, 4) (in
which case, 〈a,b〉 = A5), which contradicts the minimality of S. This completes the proof of the claim.
We have the following two hamiltonian cycles (see notes 4.13 and 4.14):
C1 =
(
a,c−1,a,b,a,c,a,b 2,a,b,c,b−1,a,b−2,a,c−1,a,c−1,b 2,c,b−2,a,b−2,c,a,b,c−1,
b−1,a,c−1,a,b−2,a,b−1,c,a,b 2,a,b,c,b−1,a,c−1,b 2,c,a,b,c−1,a,b−1,a,b
)
and
C2 =
(
a,c−1,a,b,a,c,a,b 2,a,b,c,b−1,a,c−1,b 2,c,a,b,c−1,b−1,a,b−2,a,c−1,b,a,b 2,
a,c,a,b,c−1,b−1,a,c−1,a,c−1,b 2,c,b−2,a,b−2,c,a,b 2,a,b,c−1,a,b−1,a,b
)
Then
[
wtC1 (b), wtC1 (c)
]
= [1, 0] and
[
wtC2 (b), wtC2 (c)
]
= [7,−2]. Since det
[
1 0
7 −2
]
= −2 6≡ 0 (mod p),
Theorem 2.11 applies.
Subcase 2.4. Assume |a| = |b| = 2 and |c| = 3. We may assume c = (1, 2, 3).
19
D. W. Morris / J. Algebra Comb. Discrete Appl. 3(1) (2016) 13–30
• Suppose a interchanges 4 and 5. This means that one of the 2-cycles in a is (4, 5). The other 2-cycle
must be contained in {1, 2, 3}, so, after conjugating by a power of c, we may assume a = (1, 2)(4, 5).
Since 〈a,b,c〉 is transitive on {1, 2, 3, 4, 5}, the permutation b cannot have (4, 5) as one of its 2-cycles.
So no 2-cycle in b is disjoint from the support of c. Since 〈b,c〉 6= A5 (by the minimality of S), this
implies that one of the 2-cycles must be contained in the support of c, which is {1, 2, 3}. So b fixes
either 4 or 5. We may assume it is 5 that is fixed (after conjugating by (4, 5) if necessary). Then
b is either (1, 2)(3, 4) or (1, 3)(2, 4) or (2, 3)(1, 4). Since the last two are conjugate by (1, 2) (which
centralizes a and inverts b), they do not both need to be considered.
– If b = (1, 2)(3, 4), we have the following hamiltonian cycle (see note 4.15):
C =
(
a,c−1, (a,b)2,a,c−1,a,b,c−1,b,c, (b,a)2,c, (a,b)2,a,c, (a,b)2,
a,c 2,b,c−1,b, (a,b)2,c−2,
(
(a,b)2,a,c−1
)2
,c−1,b,a,c−1, (a,b)2
)
.
Since wtC (c) = −5 6≡ 0 (mod p), Theorem 2.11 applies.
– If b = (1, 3)(2, 4), we have the following hamiltonian cycle (see note 4.16):
C =
(
(a,b)4,c, (a,b)4,a,c−1,b,a,b,c−1, (b,a)3,c−1,
b, (a,b)2,c,b,a,c−1, (b,a)4,b,c, (a,b)4,a,c−1,b
)
.
Since wtC (c) = −2 6≡ 0 (mod p), Theorem 2.11 applies.
• We may now assume that neither a nor b interchanges 4 and 5. Since 〈a,c〉 6= A5, and a does not
interchange 4 and 5, we see that a must fix either 4 or 5. Similarly for b. Furthermore, a and b
cannot both fix 4 (or 5), since 〈a,b,c〉 is transitive. So one of them fixes 4, and the other fixes 5.
We may assume it is a that fixes 5. Then we may assume a = (1, 2)(3, 4), after conjugating by a
power of c. Then b must be either (1, 2)(3, 5) or (1, 3)(2, 5) or (1, 5)(2, 3). However, the last two are
conjugate by (1, 2) (which centralizes a and inverts c), so they do not both need to be considered.
– If b = (1, 2)(3, 5), then we have the hamiltonian cycle (see note 4.17):
C =
(
a,c−1,a,c,b, (a,b)2,c, (a,b)2, (a,c)2,a,b,a,c−2,a,c−1,b,a,
c,b,a,b,c 2,
(
(a,b)2,a,c
)2
, (a,c−1)2, (a,b)2,a,c−2, (a,b)2
)
.
Since wtC (c) = 1 6≡ 0 (mod p), Theorem 2.11 applies.
– If b = (1, 3)(2, 5), then we have the following hamiltonian cycle (see note 4.18):
C =
(
a,b,c−1, (a,b)2,a,c,b, (a,b)4,c, (a,b,a,c−1)2,b,a,b,c 2,
(a,b)2,a,c,
(
(b,a)2,c−1
)2
, (b,a)2,b,c−1, (b,a)2,c−1,b
)
.
Since wtC (c) = −2 6≡ 0 (mod p), Theorem 2.11 applies.
Subcase 2.5. Assume |a| = |b| = |c| = 2. Since all generators are of order 2, Theorem 2.9
applies.
20
D. W. Morris / J. Algebra Comb. Discrete Appl. 3(1) (2016) 13–30
4. Details of hamiltonian cycles in A5
To aid the reader in validating the many hamiltonian cycles in A5 that appeared in the proof of
Theorem 1.2, this final section provides a list of the vertices in the order that they are visited by each
cycle.
4.1. A hamiltonian cycle in Cay(A5; a,b) with a = (1, 2)(3, 4) and b = (2, 4, 5).
e
a−→ (1, 2)(3, 4) b−→ (1, 2, 3, 4, 5) b−→ (1, 2, 5, 3, 4) a−→ (1, 5, 3)
b−→ (1, 5, 2, 4, 3) b−→ (1, 5, 4, 2, 3) a−→ (1, 3, 2, 5, 4) b−→ (1, 3, 2) b−→ (1, 3, 2, 4, 5)
a−→ (1, 4, 2, 3, 5) b
−1
−→ (1, 4, 3, 5, 2) b
−1
−→ (1, 4)(3, 5) a−→ (1, 2, 4, 5, 3) b
−1
−→ (1, 2, 3)
b−1−→ (1, 2, 5, 4, 3) a−→ (1, 5, 4) b
−1
−→ (1, 5)(2, 4) b
−1
−→ (1, 5, 2) a−→ (2, 5)(3, 4)
b−→ (2, 3, 4) b−→ (3, 4, 5) a−→ (1, 2)(3, 5) b
−1
−→ (1, 2, 3, 5, 4) b
−1
−→ (1, 2, 4, 3, 5)
a−→ (1, 4, 5) b−→ (1, 4)(2, 5) b−→ (1, 4, 2) a−→ (2, 4, 3) b
−1
−→ (2, 5, 3)
b−1−→ (2, 3)(4, 5) a−→ (1, 3, 5, 4, 2) b−→ (1, 3, 5) b−→ (1, 3, 5, 2, 4) a−→ (1, 4, 5, 2, 3)
b−→ (1, 4, 2, 5, 3) b−→ (1, 4, 3) a−→ (1, 2, 4) b−→ (1, 2)(4, 5) b−→ (1, 2, 5)
a−→ (1, 5)(3, 4) b
−1
−→ (1, 5, 3, 4, 2) b
−1
−→ (1, 5, 2, 3, 4) a−→ (1, 3)(2, 5) b
−1
−→ (1, 3)(4, 5)
b−1−→ (1, 3)(2, 4) a−→ (1, 4)(2, 3) b
−1
−→ (1, 4, 3, 2, 5) b
−1
−→ (1, 4, 5, 3, 2) a−→ (2, 4)(3, 5)
b−→ (3, 5, 4) b−→ (2, 3, 5) a−→ (1, 3, 4, 5, 2) b
−1
−→ (1, 3, 4) b
−1
−→ (1, 3, 4, 2, 5)
a−→ (1, 5)(2, 3) b−→ (1, 5, 3, 2, 4) b−→ (1, 5, 4, 3, 2) a−→ (2, 5, 4) b
−1
−→ (2, 4, 5)
b−1−→ e
4.2. A hamiltonian cycle in Cay(A5; a,b) with a = (1, 2)(3, 4) and b = (1, 2, 3, 4, 5).
e
a−→ (1, 2)(3, 4) b−→ (2, 4, 5) a−→ (1, 4, 3, 5, 2) b−→ (2, 5, 4)
b−→ (1, 5)(2, 3) b−→ (1, 3, 4) b−→ (1, 2, 4, 5, 3) a−→ (1, 4)(3, 5) b−→ (1, 2, 5, 4, 3)
a−→ (1, 5, 4) b−→ (1, 2, 3) b−→ (1, 3, 4, 5, 2) b−→ (2, 4)(3, 5) b−→ (1, 4, 3, 2, 5)
a−→ (1, 5)(2, 4) b−→ (1, 4)(2, 3) b−→ (1, 3)(4, 5) a−→ (1, 2, 3, 5, 4) b
−1
−→ (1, 4, 5)
a−→ (1, 2, 4, 3, 5) b−→ (1, 4)(2, 5) b−→ (1, 5, 4, 2, 3) b−→ (1, 3, 2) b−→ (3, 4, 5)
a−→ (1, 2)(3, 5) b−→ (2, 5)(3, 4) a−→ (1, 5, 2) b−→ (2, 3, 4) b−→ (1, 3, 2, 4, 5)
a−→ (1, 4, 2, 3, 5) b−→ (1, 3, 2, 5, 4) b−→ (1, 5, 3) a−→ (1, 2, 5, 3, 4) b−→ (1, 5, 2, 4, 3)
b−→ (1, 4, 2) a−→ (2, 4, 3) b
−1
−→ (1, 5, 3, 4, 2) b
−1
−→ (1, 3)(2, 5) a−→ (1, 5, 2, 3, 4)
b−→ (1, 3)(2, 4) b−→ (1, 4, 5, 3, 2) b−→ (3, 5, 4) b−→ (1, 2, 5) a−→ (1, 5)(3, 4)
b−1−→ (2, 5, 3) b
−1
−→ (1, 3, 5, 4, 2) a−→ (2, 3)(4, 5) b−→ (1, 3, 5) a−→ (1, 2, 3, 4, 5)
b−→ (1, 3, 5, 2, 4) a−→ (1, 4, 5, 2, 3) b
−1
−→ (1, 2, 4) a−→ (1, 4, 3) b−→ (1, 2)(4, 5)
b−→ (2, 3, 5) b−→ (1, 3, 4, 2, 5) b−→ (1, 5, 3, 2, 4) a−→ (1, 4, 2, 5, 3) b−→ (1, 5, 4, 3, 2)
b−→ e
21
D. W. Morris / J. Algebra Comb. Discrete Appl. 3(1) (2016) 13–30
4.3. A hamiltonian cycle in Cay(A5; a,b) with a = (1, 3)(2, 4) and b = (1, 2, 3, 4, 5).
e
a−→ (1, 3)(2, 4) b−→ (1, 4, 5, 3, 2) b−→ (3, 5, 4) b−→ (1, 2, 5)
b−→ (1, 5, 2, 3, 4) a−→ (1, 4, 3, 5, 2) b
−1
−→ (1, 2, 4, 5, 3) a−→ (2, 5, 3) b−→ (1, 5)(3, 4)
a−→ (1, 4, 2, 3, 5) b
−1
−→ (2, 4, 5) a−→ (1, 3)(2, 5) b
−1
−→ (1, 2, 3, 5, 4) b
−1
−→ (1, 4, 5)
b−1−→ (2, 4, 3) b
−1
−→ (1, 5, 3, 4, 2) a−→ (1, 4)(3, 5) b
−1
−→ (1, 3, 2, 4, 5) b
−1
−→ (2, 3, 4)
a−→ (1, 4, 3) b
−1
−→ (1, 5, 3, 2, 4) b
−1
−→ (1, 3, 4, 2, 5) b
−1
−→ (2, 3, 5) b
−1
−→ (1, 2)(4, 5)
a−→ (1, 3, 2, 5, 4) b−→ (1, 5, 3) b−→ (1, 2)(3, 4) a−→ (1, 4)(2, 3) b
−1
−→ (1, 5)(2, 4)
b−1−→ (2, 5)(3, 4) b
−1
−→ (1, 2)(3, 5) b
−1
−→ (1, 3)(4, 5) a−→ (2, 5, 4) b−→ (1, 5)(2, 3)
b−→ (1, 3, 4) a−→ (1, 4, 2) b
−1
−→ (1, 5, 2, 4, 3) b
−1
−→ (1, 2, 5, 3, 4) b
−1
−→ (1, 3, 5)
b−1−→ (2, 3)(4, 5) a−→ (1, 2, 5, 4, 3) b−→ (1, 5, 2) a−→ (1, 3, 5, 2, 4) b
−1
−→ (1, 2, 3, 4, 5)
a−→ (1, 4, 3, 2, 5) b
−1
−→ (2, 4)(3, 5) b
−1
−→ (1, 3, 4, 5, 2) b
−1
−→ (1, 2, 3) b
−1
−→ (1, 5, 4)
a−→ (1, 3, 5, 4, 2) b
−1
−→ (1, 4, 5, 2, 3) b
−1
−→ (1, 2, 4) a−→ (1, 3, 2) b
−1
−→ (1, 5, 4, 2, 3)
b−1−→ (1, 4)(2, 5) b
−1
−→ (1, 2, 4, 3, 5) b
−1
−→ (3, 4, 5) a−→ (1, 4, 2, 5, 3) b−→ (1, 5, 4, 3, 2)
b−→ e
4.4. A hamiltonian cycle C1 in Cay(A5; a,b) with a = (1, 2, 3) and b = (3, 4, 5).
e
b−→ (3, 4, 5) a−→ (1, 2, 4, 5, 3) b−→ (1, 2, 4, 3, 5) b−→ (1, 2, 4)
a−→ (1, 4)(2, 3) a−→ (1, 3, 4) b
−1
−→ (1, 3, 5) b
−1
−→ (1, 3)(4, 5) a
−1
−→ (2, 3)(4, 5)
a−1−→ (1, 2)(4, 5) b−→ (1, 2)(3, 5) b−→ (1, 2)(3, 4) a−→ (2, 4, 3) a−→ (1, 4, 3)
b−→ (1, 4, 5) b−→ (1, 4)(3, 5) a
−1
−→ (1, 5, 3, 2, 4) a
−1
−→ (1, 2, 5, 3, 4) b
−1
−→ (1, 2, 5)
b−1−→ (1, 2, 5, 4, 3) a
−1
−→ (3, 5, 4) a
−1
−→ (1, 5, 4, 3, 2) b−→ (1, 5, 2) b−→ (1, 5, 3, 4, 2)
a−→ (2, 4)(3, 5) a−→ (1, 4, 2, 5, 3) b
−1
−→ (1, 4)(2, 5) b
−1
−→ (1, 4, 3, 2, 5) a−→ (1, 5)(3, 4)
b−1−→ (1, 5, 3) b
−1
−→ (1, 5, 4) a
−1
−→ (1, 3, 2, 5, 4) a
−1
−→ (1, 2, 3, 5, 4) b−→ (1, 2, 3)
b−→ (1, 2, 3, 4, 5) a−→ (1, 3, 2, 4, 5) b−→ (1, 3, 5, 2, 4) a
−1
−→ (1, 5, 2, 3, 4) b
−1
−→ (1, 5)(2, 3)
b−1−→ (1, 5, 4, 2, 3) a−→ (1, 3, 5, 4, 2) a−→ (2, 5, 4) b−→ (2, 5, 3) b−→ (2, 5)(3, 4)
a−→ (1, 5, 2, 4, 3) a−→ (1, 4, 3, 5, 2) b
−1
−→ (1, 4, 5, 3, 2) b
−1
−→ (1, 4, 2) a
−1
−→ (1, 3)(2, 4)
a−1−→ (2, 3, 4) b
−1
−→ (2, 3, 5) a−→ (1, 3)(2, 5) b−→ (1, 3, 4, 2, 5) a−→ (1, 5)(2, 4)
a−→ (1, 4, 2, 3, 5) b
−1
−→ (1, 4, 5, 2, 3) a
−1
−→ (2, 4, 5) a
−1
−→ (1, 3, 4, 5, 2) b
−1
−→ (1, 3, 2)
a−→ e
22
D. W. Morris / J. Algebra Comb. Discrete Appl. 3(1) (2016) 13–30
4.5. A hamiltonian cycle C1 in Cay(A5; a,b) with a = (1, 2, 4) and b = (1, 2, 3, 4, 5).
e
a−→ (1, 2, 4) a−→ (1, 4, 2) b
−1
−→ (1, 5, 2, 4, 3) b
−1
−→ (1, 2, 5, 3, 4)
a−1−→ (3, 4, 5) a
−1
−→ (1, 5, 3, 4, 2) b
−1
−→ (1, 3)(2, 5) a
−1
−→ (1, 4, 5, 2, 3) b−→ (1, 3, 5, 4, 2)
a−→ (3, 5, 4) a−→ (1, 2, 3, 5, 4) b
−1
−→ (1, 4, 5) a
−1
−→ (1, 5)(2, 4) a
−1
−→ (1, 2, 5)
b−→ (1, 5, 2, 3, 4) a
−1
−→ (2, 5)(3, 4) a
−1
−→ (1, 3, 4, 5, 2) b
−1
−→ (1, 2, 3) b
−1
−→ (1, 5, 4)
a−1−→ (2, 5, 4) a
−1
−→ (1, 2)(4, 5) b
−1
−→ (1, 4, 3) a
−1
−→ (1, 3)(2, 4) b−→ (1, 4, 5, 3, 2)
a−→ (2, 5, 3) a−→ (1, 5, 3, 2, 4) b
−1
−→ (1, 3, 4, 2, 5) a−→ (1, 5)(3, 4) a−→ (1, 2, 3, 4, 5)
b−→ (1, 3, 5, 2, 4) a
−1
−→ (2, 3, 5) a
−1
−→ (1, 4, 3, 5, 2) b
−1
−→ (1, 2, 4, 5, 3) a−→ (1, 4, 2, 5, 3)
a−→ (1, 5, 3) b−→ (1, 2)(3, 4) a−→ (2, 3, 4) a−→ (1, 3, 4) b
−1
−→ (1, 5)(2, 3)
a−1−→ (1, 4, 3, 2, 5) a
−1
−→ (1, 3, 2, 4, 5) b−→ (1, 4)(3, 5) a
−1
−→ (2, 4)(3, 5) a
−1
−→ (1, 2)(3, 5)
b−1−→ (1, 3)(4, 5) b
−1
−→ (1, 4)(2, 3) a
−1
−→ (2, 4, 3) a
−1
−→ (1, 3, 2) b
−1
−→ (1, 5, 4, 2, 3)
a−1−→ (1, 2, 5, 4, 3) b−→ (1, 5, 2) a−→ (2, 4, 5) a−→ (1, 4)(2, 5) b
−1
−→ (1, 2, 4, 3, 5)
a−1−→ (1, 3, 5) a
−1
−→ (1, 4, 2, 3, 5) b−→ (1, 3, 2, 5, 4) a
−1
−→ (2, 3)(4, 5) a
−1
−→ (1, 5, 4, 3, 2)
b−→ e
4.6. A second hamiltonian cycle C2 in Cay(A5; a,b) with a = (1, 2, 4) and b = (1, 2, 3, 4, 5).
e
a−→ (1, 2, 4) a−→ (1, 4, 2) b
−1
−→ (1, 5, 2, 4, 3) b
−1
−→ (1, 2, 5, 3, 4)
a−1−→ (3, 4, 5) a
−1
−→ (1, 5, 3, 4, 2) b
−1
−→ (1, 3)(2, 5) a
−1
−→ (1, 4, 5, 2, 3) b−→ (1, 3, 5, 4, 2)
a−→ (3, 5, 4) a−→ (1, 2, 3, 5, 4) b
−1
−→ (1, 4, 5) a−→ (1, 2, 5) a−→ (1, 5)(2, 4)
b−1−→ (2, 5)(3, 4) a−→ (1, 5, 2, 3, 4) a−→ (1, 3, 4, 5, 2) b
−1
−→ (1, 2, 3) b
−1
−→ (1, 5, 4)
a−1−→ (2, 5, 4) a
−1
−→ (1, 2)(4, 5) b
−1
−→ (1, 4, 3) a
−1
−→ (1, 3)(2, 4) b−→ (1, 4, 5, 3, 2)
a−→ (2, 5, 3) a−→ (1, 5, 3, 2, 4) b
−1
−→ (1, 3, 4, 2, 5) a−→ (1, 5)(3, 4) a−→ (1, 2, 3, 4, 5)
b−→ (1, 3, 5, 2, 4) a
−1
−→ (2, 3, 5) a
−1
−→ (1, 4, 3, 5, 2) b
−1
−→ (1, 2, 4, 5, 3) a−→ (1, 4, 2, 5, 3)
a−→ (1, 5, 3) b−→ (1, 2)(3, 4) a−→ (2, 3, 4) a−→ (1, 3, 4) b
−1
−→ (1, 5)(2, 3)
a−1−→ (1, 4, 3, 2, 5) a
−1
−→ (1, 3, 2, 4, 5) b−→ (1, 4)(3, 5) a
−1
−→ (2, 4)(3, 5) a
−1
−→ (1, 2)(3, 5)
b−1−→ (1, 3)(4, 5) b
−1
−→ (1, 4)(2, 3) a
−1
−→ (2, 4, 3) a
−1
−→ (1, 3, 2) b
−1
−→ (1, 5, 4, 2, 3)
a−1−→ (1, 2, 5, 4, 3) b−→ (1, 5, 2) a−→ (2, 4, 5) a−→ (1, 4)(2, 5) b
−1
−→ (1, 2, 4, 3, 5)
a−1−→ (1, 3, 5) a
−1
−→ (1, 4, 2, 3, 5) b−→ (1, 3, 2, 5, 4) a
−1
−→ (2, 3)(4, 5) a
−1
−→ (1, 5, 4, 3, 2)
b−→ e
23
D. W. Morris / J. Algebra Comb. Discrete Appl. 3(1) (2016) 13–30
4.7. A hamiltonian cycle C1 in Cay(A5; a,b) with a = (1, 2, 3) and b = (1, 2, 3, 4, 5).
e
a−→ (1, 2, 3) a−→ (1, 3, 2) b
−1
−→ (1, 5, 4, 2, 3) b
−1
−→ (1, 4)(2, 5)
a−1−→ (1, 3, 5, 2, 4) a
−1
−→ (1, 5, 2, 3, 4) b
−1
−→ (1, 2, 5) a
−1
−→ (1, 3, 5) b−→ (1, 2, 5, 3, 4)
b−→ (1, 5, 2, 4, 3) b−→ (1, 4, 2) a−→ (2, 3, 4) a−→ (1, 3)(2, 4) b−→ (1, 4, 5, 3, 2)
a−→ (3, 4, 5) a−→ (1, 2, 4, 5, 3) b−→ (1, 4, 3, 5, 2) a−→ (2, 5)(3, 4) b
−1
−→ (1, 2)(3, 5)
a−→ (2, 5, 3) a−→ (1, 5, 3) b−→ (1, 2)(3, 4) a−→ (2, 4, 3) a−→ (1, 4, 3)
b−→ (1, 2)(4, 5) a−→ (2, 3)(4, 5) a−→ (1, 3)(4, 5) b
−1
−→ (1, 4)(2, 3) b
−1
−→ (1, 5)(2, 4)
a−→ (1, 4, 2, 3, 5) a−→ (1, 3, 4, 2, 5) b−→ (1, 5, 3, 2, 4) a−→ (1, 4)(3, 5) b
−1
−→ (1, 3, 2, 4, 5)
a−1−→ (1, 2, 3, 4, 5) a
−1
−→ (1, 4, 5) b−→ (1, 2, 3, 5, 4) a−→ (1, 3, 2, 5, 4) a−→ (1, 5, 4)
b−1−→ (1, 4, 3, 2, 5) a
−1
−→ (1, 2, 4, 3, 5) a
−1
−→ (1, 5)(3, 4) b−→ (1, 2, 4) a
−1
−→ (1, 3, 4)
b−1−→ (1, 5)(2, 3) b
−1
−→ (2, 5, 4) a
−1
−→ (1, 3, 5, 4, 2) b
−1
−→ (1, 4, 5, 2, 3) a
−1
−→ (2, 4, 5)
a−1−→ (1, 3, 4, 5, 2) b−→ (2, 4)(3, 5) a−→ (1, 4, 2, 5, 3) a−→ (1, 5, 3, 4, 2) b
−1
−→ (1, 3)(2, 5)
a−1−→ (2, 3, 5) a
−1
−→ (1, 5, 2) b
−1
−→ (1, 2, 5, 4, 3) a
−1
−→ (3, 5, 4) a
−1
−→ (1, 5, 4, 3, 2)
b−→ e
4.8. A second hamiltonian cycle C2 in Cay(A5; a,b) with a = (1, 2, 3) and b = (1, 2, 3, 4, 5).
e
a−→ (1, 2, 3) a−→ (1, 3, 2) b
−1
−→ (1, 5, 4, 2, 3) a−→ (1, 3, 5, 4, 2)
a−→ (2, 5, 4) b−→ (1, 5)(2, 3) a−→ (1, 3, 5) a−→ (1, 2, 5) b−→ (1, 5, 2, 3, 4)
a−→ (1, 3, 5, 2, 4) a−→ (1, 4)(2, 5) b
−1
−→ (1, 2, 4, 3, 5) a
−1
−→ (1, 5)(3, 4) a
−1
−→ (1, 4, 3, 2, 5)
b−→ (1, 5, 4) a
−1
−→ (1, 3, 2, 5, 4) a
−1
−→ (1, 2, 3, 5, 4) b
−1
−→ (1, 4, 5) a−→ (1, 2, 3, 4, 5)
a−→ (1, 3, 2, 4, 5) b−→ (1, 4)(3, 5) a−→ (1, 2, 5, 3, 4) a−→ (1, 5, 3, 2, 4) b
−1
−→ (1, 3, 4, 2, 5)
a−1−→ (1, 4, 2, 3, 5) a
−1
−→ (1, 5)(2, 4) b−→ (1, 4)(2, 3) b−→ (1, 3)(4, 5) a
−1
−→ (2, 3)(4, 5)
a−1−→ (1, 2)(4, 5) b
−1
−→ (1, 4, 3) a
−1
−→ (2, 4, 3) a
−1
−→ (1, 2)(3, 4) b
−1
−→ (1, 5, 3)
a−1−→ (2, 5, 3) a
−1
−→ (1, 2)(3, 5) b−→ (2, 5)(3, 4) a
−1
−→ (1, 4, 3, 5, 2) a
−1
−→ (1, 5, 2, 4, 3)
b−→ (1, 4, 2) a−→ (2, 3, 4) a−→ (1, 3)(2, 4) b−→ (1, 4, 5, 3, 2) a−→ (3, 4, 5)
a−→ (1, 2, 4, 5, 3) b
−1
−→ (1, 3, 4) a−→ (1, 2, 4) b−→ (1, 4, 5, 2, 3) a
−1
−→ (2, 4, 5)
a−1−→ (1, 3, 4, 5, 2) b−→ (2, 4)(3, 5) a−→ (1, 4, 2, 5, 3) a−→ (1, 5, 3, 4, 2) b
−1
−→ (1, 3)(2, 5)
a−1−→ (2, 3, 5) a
−1
−→ (1, 5, 2) b
−1
−→ (1, 2, 5, 4, 3) a
−1
−→ (3, 5, 4) a
−1
−→ (1, 5, 4, 3, 2)
b−→ e
24
D. W. Morris / J. Algebra Comb. Discrete Appl. 3(1) (2016) 13–30
4.9. A hamiltonian cycle C1 in Cay(A5; a,b) with a = (1, 2, 3, 4, 5) and b = (1, 2, 3, 5, 4).
e
b−→ (1, 2, 3, 5, 4) a
−1
−→ (1, 4, 5) b−→ (1, 2, 3) a−→ (1, 3, 4, 5, 2)
b−→ (2, 4, 3) b−→ (1, 4)(3, 5) b−→ (1, 2, 5) b−→ (1, 5, 4, 2, 3) a−→ (1, 3, 2)
b−→ (3, 5, 4) b−→ (1, 2, 5, 3, 4) a
−1
−→ (1, 3, 5) b−→ (1, 2, 5, 4, 3) b−→ (1, 5, 3, 4, 2)
a−1−→ (1, 3)(2, 5) b
−1
−→ (1, 4, 2, 3, 5) a
−1
−→ (2, 4, 5) b−→ (1, 4)(2, 3) a
−1
−→ (1, 5)(2, 4)
b−→ (1, 4, 5, 2, 3) a−→ (1, 3, 5, 4, 2) b−→ (2, 5)(3, 4) b−→ (1, 5, 3, 2, 4) a
−1
−→ (1, 3, 4, 2, 5)
b−→ (1, 5, 2, 4, 3) b−→ (1, 4, 5, 3, 2) a
−1
−→ (1, 3)(2, 4) b
−1
−→ (1, 2, 3, 4, 5) a−→ (1, 3, 5, 2, 4)
b−1−→ (2, 3, 4) b
−1
−→ (1, 2)(4, 5) a
−1
−→ (1, 4, 3) b
−1
−→ (1, 3, 2, 4, 5) b
−1
−→ (1, 5, 2, 3, 4)
b−1−→ (2, 5, 4) b
−1
−→ (1, 2)(3, 5) a
−1
−→ (1, 3)(4, 5) b
−1
−→ (1, 5)(2, 3) a−→ (1, 3, 4)
b−1−→ (2, 3)(4, 5) b
−1
−→ (1, 5, 2) b
−1
−→ (1, 4, 2, 5, 3) b
−1
−→ (1, 2, 4, 3, 5) a−→ (1, 4)(2, 5)
b−1−→ (2, 4)(3, 5) b
−1
−→ (1, 2)(3, 4) a
−1
−→ (1, 5, 3) b
−1
−→ (1, 4, 3, 2, 5) a−→ (1, 5, 4)
b−1−→ (2, 5, 3) b
−1
−→ (1, 4, 3, 5, 2) a
−1
−→ (1, 2, 4, 5, 3) b−→ (1, 4, 2) b−→ (2, 3, 5)
b−→ (1, 3, 2, 5, 4) b−→ (1, 5)(3, 4) a−→ (1, 2, 4) b
−1
−→ (3, 4, 5) b
−1
−→ (1, 5, 4, 3, 2)
a−→ e
4.10. A hamiltonian cycle C1 in Cay(A5; a,b) with a = (1, 2, 3, 4, 5) and b = (1, 3, 4, 2, 5).
e
a−→ (1, 2, 3, 4, 5) a−→ (1, 3, 5, 2, 4) a−→ (1, 4, 2, 5, 3) a−→ (1, 5, 4, 3, 2)
b−1−→ (1, 4, 2, 3, 5) a
−1
−→ (2, 4, 5) a
−1
−→ (1, 2)(3, 4) a
−1
−→ (1, 5, 3) a
−1
−→ (1, 3, 2, 5, 4)
b−→ (1, 2, 4, 5, 3) a−→ (1, 4, 3, 5, 2) a−→ (2, 5, 4) a−→ (1, 5)(2, 3) a−→ (1, 3, 4)
b−1−→ (1, 5, 2) a−→ (2, 3, 4) a−→ (1, 3, 2, 4, 5) b−→ (1, 2)(3, 5) a
−1
−→ (1, 3)(4, 5)
a−1−→ (1, 4)(2, 3) b−→ (1, 2, 5, 4, 3) a
−1
−→ (1, 4)(3, 5) b−→ (1, 5, 4, 2, 3) a
−1
−→ (1, 4)(2, 5)
a−1−→ (1, 2, 4, 3, 5) a
−1
−→ (3, 4, 5) a
−1
−→ (1, 3, 2) b
−1
−→ (1, 5)(2, 4) a
−1
−→ (2, 5)(3, 4)
b−1−→ (1, 2, 3) a−→ (1, 3, 4, 5, 2) a−→ (2, 4)(3, 5) a−→ (1, 4, 3, 2, 5) a−→ (1, 5, 4)
b−→ (1, 3)(2, 4) a
−1
−→ (1, 5, 2, 3, 4) a
−1
−→ (1, 2, 5) a
−1
−→ (3, 5, 4) a
−1
−→ (1, 4, 5, 3, 2)
b−1−→ (1, 3, 4, 2, 5) a
−1
−→ (2, 3, 5) a
−1
−→ (1, 2)(4, 5) a
−1
−→ (1, 4, 3) a
−1
−→ (1, 5, 3, 2, 4)
b−1−→ (1, 3, 5, 4, 2) a−→ (2, 5, 3) a−→ (1, 5)(3, 4) b−→ (1, 4, 2) a−→ (2, 3)(4, 5)
a−→ (1, 3, 5) b−→ (1, 5, 3, 4, 2) a−→ (2, 4, 3) a−→ (1, 4, 5) a−→ (1, 2, 3, 5, 4)
a−→ (1, 3)(2, 5) b
−1
−→ (1, 2, 4) a−→ (1, 4, 5, 2, 3) b
−1
−→ (1, 2, 5, 3, 4) a−→ (1, 5, 2, 4, 3)
b−→ e
25
D. W. Morris / J. Algebra Comb. Discrete Appl. 3(1) (2016) 13–30
4.11. A second hamiltonian cycle C2 in Cay(A5; a,b) with a = (1, 2, 3, 4, 5) and b = (1, 3, 4, 2, 5).
e
a−→ (1, 2, 3, 4, 5) a−→ (1, 3, 5, 2, 4) a−→ (1, 4, 2, 5, 3) a−→ (1, 5, 4, 3, 2)
b−1−→ (1, 4, 2, 3, 5) a
−1
−→ (2, 4, 5) a
−1
−→ (1, 2)(3, 4) a
−1
−→ (1, 5, 3) a
−1
−→ (1, 3, 2, 5, 4)
b−→ (1, 2, 4, 5, 3) a−→ (1, 4, 3, 5, 2) a−→ (2, 5, 4) a−→ (1, 5)(2, 3) a−→ (1, 3, 4)
b−1−→ (1, 5, 2) a−→ (2, 3, 4) a−→ (1, 3, 2, 4, 5) b−→ (1, 2)(3, 5) a
−1
−→ (1, 3)(4, 5)
b−1−→ (1, 4)(2, 5) a
−1
−→ (1, 2, 4, 3, 5) a
−1
−→ (3, 4, 5) a
−1
−→ (1, 3, 2) a
−1
−→ (1, 5, 4, 2, 3)
b−1−→ (1, 4)(3, 5) a−→ (1, 2, 5, 4, 3) b
−1
−→ (1, 4)(2, 3) a
−1
−→ (1, 5)(2, 4) a
−1
−→ (2, 5)(3, 4)
b−1−→ (1, 2, 3) a−→ (1, 3, 4, 5, 2) a−→ (2, 4)(3, 5) a−→ (1, 4, 3, 2, 5) a−→ (1, 5, 4)
b−→ (1, 3)(2, 4) a
−1
−→ (1, 5, 2, 3, 4) a
−1
−→ (1, 2, 5) a
−1
−→ (3, 5, 4) a
−1
−→ (1, 4, 5, 3, 2)
b−1−→ (1, 3, 4, 2, 5) a
−1
−→ (2, 3, 5) a
−1
−→ (1, 2)(4, 5) a
−1
−→ (1, 4, 3) a
−1
−→ (1, 5, 3, 2, 4)
b−1−→ (1, 3, 5, 4, 2) a−→ (2, 5, 3) a−→ (1, 5)(3, 4) b−→ (1, 4, 2) a−→ (2, 3)(4, 5)
a−→ (1, 3, 5) b−→ (1, 5, 3, 4, 2) a−→ (2, 4, 3) a−→ (1, 4, 5) a−→ (1, 2, 3, 5, 4)
a−→ (1, 3)(2, 5) b
−1
−→ (1, 2, 4) a−→ (1, 4, 5, 2, 3) b
−1
−→ (1, 2, 5, 3, 4) a−→ (1, 5, 2, 4, 3)
b−→ e
4.12. A hamiltonian cycle R1 in Cay(A5; a,b,c) with a = (1, 2, 5), b = (1, 3, 5), and c = (1, 4, 5).
e
a−→ (1, 2, 5) a−→ (1, 5, 2) b−→ (1, 3, 2) a−→ (2, 5, 3)
a−→ (1, 5)(2, 3) b−→ (1, 2, 3) a−→ (1, 3)(2, 5) a−→ (1, 5, 3) c−→ (1, 4, 3)
a−→ (1, 2, 5, 4, 3) a−→ (1, 5, 2, 4, 3) b−→ (2, 4, 3) a−→ (1, 4, 3, 2, 5) a−→ (1, 5, 4, 3, 2)
b−→ (1, 2)(3, 4) a−→ (2, 5)(3, 4) a−→ (1, 5)(3, 4) c−→ (1, 3, 4) a−→ (1, 2, 5, 3, 4)
b−→ (1, 4)(2, 5) b−→ (1, 3, 2, 5, 4) a−→ (1, 5, 3, 2, 4) a−→ (1, 4)(2, 3) b−→ (1, 2, 3, 5, 4)
a−→ (1, 3, 5, 2, 4) a−→ (1, 4)(3, 5) c−→ (3, 5, 4) c−→ (1, 3, 5) a−→ (1, 2)(3, 5)
a−→ (2, 3, 5) c−→ (1, 4, 2, 3, 5) b−→ (1, 5, 4, 2, 3) a−→ (1, 3)(2, 4) b−→ (2, 4)(3, 5)
c−→ (1, 2, 4, 3, 5) a−→ (1, 4, 3, 5, 2) c−→ (1, 3, 5, 4, 2) b−→ (1, 5, 3, 4, 2) b−→ (1, 4, 2)
c−→ (1, 2)(4, 5) b−→ (1, 3, 4, 5, 2) b−→ (1, 4, 5, 3, 2) a−→ (2, 3)(4, 5) a−→ (1, 3, 2, 4, 5)
b−→ (1, 2, 4, 5, 3) a−→ (1, 4, 5, 2, 3) a−→ (1, 3)(4, 5) b−→ (3, 4, 5) a−→ (1, 2, 3, 4, 5)
c−→ (1, 5, 2, 3, 4) c−→ (2, 3, 4) a−→ (1, 3, 4, 2, 5) b−→ (1, 4, 2, 5, 3) b−→ (2, 5, 4)
a−→ (1, 5)(2, 4) c−→ (1, 2, 4) c−→ (2, 4, 5) a−→ (1, 4, 5) c−→ (1, 5, 4)
c−→ e
26
D. W. Morris / J. Algebra Comb. Discrete Appl. 3(1) (2016) 13–30
4.13. A hamiltonian cycle C1 in Cay(A5; a,b,c,c) with a = (1, 2)(4, 5), b = (1, 2, 3), and c = (1, 2, 4).
e
a−→ (1, 2)(4, 5) c
−1
−→ (1, 5, 4) a−→ (1, 2, 5) b−→ (1, 5)(2, 3)
a−→ (1, 3, 2, 5, 4) c−→ (1, 5, 4, 3, 2) a−→ (2, 5, 3) b−→ (1, 5, 3) b−→ (1, 2)(3, 5)
a−→ (3, 5, 4) b−→ (1, 2, 5, 4, 3) c−→ (1, 5, 4, 2, 3) b
−1
−→ (2, 5, 4) a−→ (1, 5, 2)
b−1−→ (1, 3)(2, 5) b
−1
−→ (2, 3, 5) a−→ (1, 3, 5, 4, 2) c
−1
−→ (1, 2, 3, 5, 4) a−→ (1, 3, 5)
c−1−→ (1, 4, 2, 3, 5) b−→ (1, 3, 4, 2, 5) b−→ (1, 5)(2, 4) c−→ (1, 4, 5) b
−1
−→ (1, 3, 2, 4, 5)
b−1−→ (1, 2, 3, 4, 5) a−→ (1, 3, 4) b
−1
−→ (1, 4)(2, 3) b
−1
−→ (1, 2, 4) c−→ (1, 4, 2)
a−→ (2, 4, 5) b−→ (1, 4, 5, 2, 3) c
−1
−→ (1, 5, 2, 4, 3) b
−1
−→ (2, 5)(3, 4) a−→ (1, 5, 3, 4, 2)
c−1−→ (1, 2, 5, 3, 4) a−→ (1, 5)(3, 4) b
−1
−→ (1, 4, 3, 2, 5) b
−1
−→ (1, 2, 4, 3, 5) a−→ (1, 4)(3, 5)
b−1−→ (1, 5, 3, 2, 4) c−→ (1, 4, 5, 3, 2) a−→ (2, 4, 3) b−→ (1, 4, 3) b−→ (1, 2)(3, 4)
a−→ (3, 4, 5) b−→ (1, 2, 4, 5, 3) c−→ (1, 4, 2, 5, 3) b
−1
−→ (2, 4)(3, 5) a−→ (1, 4, 3, 5, 2)
c−1−→ (1, 3, 5, 2, 4) b−→ (1, 4)(2, 5) b−→ (1, 5, 2, 3, 4) c−→ (1, 3, 4, 5, 2) a−→ (2, 3, 4)
b−→ (1, 3)(2, 4) c
−1
−→ (1, 2, 3) a−→ (1, 3)(4, 5) b
−1
−→ (2, 3)(4, 5) a−→ (1, 3, 2)
b−→ e
4.14. A second cycle C2 in Cay(A5; a,b,c) with a = (1, 2)(4, 5), b = (1, 2, 3), and c = (1, 2, 4).
e
a−→ (1, 2)(4, 5) c
−1
−→ (1, 5, 4) a−→ (1, 2, 5) b−→ (1, 5)(2, 3)
a−→ (1, 3, 2, 5, 4) c−→ (1, 5, 4, 3, 2) a−→ (2, 5, 3) b−→ (1, 5, 3) b−→ (1, 2)(3, 5)
a−→ (3, 5, 4) b−→ (1, 2, 5, 4, 3) c−→ (1, 5, 4, 2, 3) b
−1
−→ (2, 5, 4) a−→ (1, 5, 2)
c−1−→ (1, 4)(2, 5) b−→ (1, 5, 2, 3, 4) b−→ (1, 3, 5, 2, 4) c−→ (1, 4, 3, 5, 2) a−→ (2, 4)(3, 5)
b−→ (1, 4, 2, 5, 3) c
−1
−→ (1, 2, 4, 5, 3) b
−1
−→ (3, 4, 5) a−→ (1, 2)(3, 4) b
−1
−→ (1, 4, 3)
b−1−→ (2, 4, 3) a−→ (1, 4, 5, 3, 2) c
−1
−→ (1, 5, 3, 2, 4) b−→ (1, 4)(3, 5) a−→ (1, 2, 4, 3, 5)
b−→ (1, 4, 3, 2, 5) b−→ (1, 5)(3, 4) a−→ (1, 2, 5, 3, 4) c−→ (1, 5, 3, 4, 2) a−→ (2, 5)(3, 4)
b−→ (1, 5, 2, 4, 3) c
−1
−→ (1, 3)(2, 5) b
−1
−→ (2, 3, 5) a−→ (1, 3, 5, 4, 2) c
−1
−→ (1, 2, 3, 5, 4)
a−→ (1, 3, 5) c
−1
−→ (1, 4, 2, 3, 5) b−→ (1, 3, 4, 2, 5) b−→ (1, 5)(2, 4) c−→ (1, 4, 5)
b−1−→ (1, 3, 2, 4, 5) b
−1
−→ (1, 2, 3, 4, 5) a−→ (1, 3, 4) b
−1
−→ (1, 4)(2, 3) b
−1
−→ (1, 2, 4)
c−→ (1, 4, 2) a−→ (2, 4, 5) b−→ (1, 4, 5, 2, 3) b−→ (1, 3, 4, 5, 2) a−→ (2, 3, 4)
b−→ (1, 3)(2, 4) c
−1
−→ (1, 2, 3) a−→ (1, 3)(4, 5) b
−1
−→ (2, 3)(4, 5) a−→ (1, 3, 2)
b−→ e
27
D. W. Morris / J. Algebra Comb. Discrete Appl. 3(1) (2016) 13–30
4.15. A hamiltonian cycle in Cay(A5; a,b,c) with a = (1, 2)(4, 5), b = (1, 2)(3, 4), and c = (1, 2, 3).
e
a−→ (1, 2)(4, 5) c
−1
−→ (1, 3)(4, 5) a−→ (1, 2, 3) b−→ (1, 3, 4)
a−→ (1, 2, 3, 4, 5) b−→ (1, 3, 5) a−→ (1, 2, 3, 5, 4) c
−1
−→ (1, 5, 4) a−→ (1, 2, 5)
b−→ (1, 5)(3, 4) c
−1
−→ (1, 4, 3, 2, 5) b−→ (1, 5)(2, 4) c−→ (1, 4, 2, 3, 5) b−→ (1, 3, 2, 4, 5)
a−→ (1, 4)(2, 3) b−→ (1, 3)(2, 4) a−→ (1, 4, 5, 2, 3) c−→ (1, 3, 4, 5, 2) a−→ (2, 3, 4)
b−→ (1, 3, 2) a−→ (2, 3)(4, 5) b−→ (1, 3, 5, 4, 2) a−→ (2, 3, 5) c−→ (1, 3)(2, 5)
a−→ (1, 5, 4, 2, 3) b−→ (1, 3, 2, 5, 4) a−→ (1, 5)(2, 3) b−→ (1, 3, 4, 2, 5) a−→ (1, 5, 2, 3, 4)
c−→ (1, 3, 5, 2, 4) c−→ (1, 4)(2, 5) b−→ (1, 5, 2, 4, 3) c
−1
−→ (2, 5)(3, 4) b−→ (1, 5, 2)
a−→ (2, 5, 4) b−→ (1, 5, 4, 3, 2) a−→ (2, 5, 3) b−→ (1, 5, 3, 4, 2) c
−1
−→ (1, 4, 2, 5, 3)
c−1−→ (2, 4)(3, 5) a−→ (1, 4, 3, 5, 2) b−→ (2, 4, 5) a−→ (1, 4, 2) b−→ (2, 4, 3)
a−→ (1, 4, 5, 3, 2) c
−1
−→ (1, 2, 4, 5, 3) a−→ (1, 4, 3) b−→ (1, 2, 4) a−→ (1, 4, 5)
b−→ (1, 2, 4, 3, 5) a−→ (1, 4)(3, 5) c
−1
−→ (1, 5, 3, 2, 4) c
−1
−→ (1, 2, 5, 3, 4) b−→ (1, 5, 3)
a−→ (1, 2, 5, 4, 3) c
−1
−→ (3, 5, 4) a−→ (1, 2)(3, 5) b−→ (3, 4, 5) a−→ (1, 2)(3, 4)
b−→ e
4.16. A hamiltonian cycle in Cay(A5; a,b,c) with a = (1, 2)(4, 5), b = (1, 3)(2, 4), and c = (1, 2, 3).
e
a−→ (1, 2)(4, 5) b−→ (1, 3, 2, 5, 4) a−→ (1, 5)(2, 3) b−→ (1, 2, 4, 3, 5)
a−→ (1, 4)(3, 5) b−→ (1, 5, 3, 4, 2) a−→ (2, 5)(3, 4) b−→ (1, 4, 5, 2, 3) c−→ (1, 3, 4, 5, 2)
a−→ (2, 3, 4) b−→ (1, 4, 3) a−→ (1, 2, 4, 5, 3) b−→ (2, 5, 3) a−→ (1, 5, 4, 3, 2)
b−→ (1, 2, 3, 5, 4) a−→ (1, 3, 5) b−→ (1, 5)(2, 4) a−→ (1, 4)(2, 5) c
−1
−→ (1, 3, 5, 2, 4)
b−→ (1, 5, 2) a−→ (2, 5, 4) b−→ (1, 3)(4, 5) c
−1
−→ (2, 3)(4, 5) b−→ (1, 2, 5, 4, 3)
a−→ (1, 5, 3) b−→ (2, 4)(3, 5) a−→ (1, 4, 3, 5, 2) b−→ (1, 5, 2, 3, 4) a−→ (1, 3, 4, 2, 5)
c−1−→ (1, 4, 2, 3, 5) b−→ (1, 5)(3, 4) a−→ (1, 2, 5, 3, 4) b−→ (1, 4, 5, 3, 2) a−→ (2, 4, 3)
b−→ (1, 2, 3) c−→ (1, 3, 2) b−→ (1, 2, 4) a−→ (1, 4, 5) c
−1
−→ (1, 3, 2, 4, 5)
b−→ (1, 2, 5) a−→ (1, 5, 4) b−→ (1, 3, 5, 4, 2) a−→ (2, 3, 5) b−→ (1, 5, 2, 4, 3)
a−→ (1, 4, 2, 5, 3) b−→ (3, 4, 5) a−→ (1, 2)(3, 4) b−→ (1, 4)(2, 3) c−→ (1, 3, 4)
a−→ (1, 2, 3, 4, 5) b−→ (1, 4, 3, 2, 5) a−→ (1, 5, 3, 2, 4) b−→ (1, 2)(3, 5) a−→ (3, 5, 4)
b−→ (1, 5, 4, 2, 3) a−→ (1, 3)(2, 5) b−→ (2, 4, 5) a−→ (1, 4, 2) c
−1
−→ (1, 3)(2, 4)
b−→ e
28
D. W. Morris / J. Algebra Comb. Discrete Appl. 3(1) (2016) 13–30
4.17. A hamiltonian cycle in Cay(A5; a,b,c) with a = (1, 2)(3, 4), b = (1, 2)(3, 5), and c = (1, 2, 3).
e
a−→ (1, 2)(3, 4) c
−1
−→ (1, 4, 3) a−→ (1, 2, 4) c−→ (1, 4)(2, 3)
b−→ (1, 3, 5, 2, 4) a−→ (1, 4, 5, 2, 3) b−→ (1, 3, 2, 4, 5) a−→ (1, 4, 2, 3, 5) b−→ (1, 3)(2, 4)
c−→ (1, 4, 2) a−→ (2, 4, 3) b−→ (1, 4, 3, 5, 2) a−→ (2, 4, 5) b−→ (1, 4, 5, 3, 2)
a−→ (2, 4)(3, 5) c−→ (1, 4, 2, 5, 3) a−→ (1, 5, 3, 2, 4) c−→ (1, 4)(3, 5) a−→ (1, 2, 4, 5, 3)
b−→ (1, 4, 5) a−→ (1, 2, 4, 3, 5) c
−1
−→ (1, 5)(3, 4) c
−1
−→ (1, 4, 3, 2, 5) a−→ (1, 5)(2, 4)
c−1−→ (1, 3, 4, 2, 5) b−→ (1, 5, 4, 2, 3) a−→ (1, 3, 2, 5, 4) c−→ (1, 5, 4) b−→ (1, 2, 5, 3, 4)
a−→ (1, 5, 3) b−→ (1, 2, 5) c−→ (1, 5)(2, 3) c−→ (1, 3, 5) a−→ (1, 2, 3, 4, 5)
b−→ (1, 3)(4, 5) a−→ (1, 2, 3, 5, 4) b−→ (1, 3, 4) a−→ (1, 2, 3) c−→ (1, 3, 2)
a−→ (2, 3, 4) b−→ (1, 3, 5, 4, 2) a−→ (2, 3)(4, 5) b−→ (1, 3, 4, 5, 2) a−→ (2, 3, 5)
c−→ (1, 3)(2, 5) a−→ (1, 5, 2, 3, 4) c
−1
−→ (1, 4)(2, 5) a−→ (1, 5, 2, 4, 3) c
−1
−→ (2, 5)(3, 4)
a−→ (1, 5, 2) b−→ (2, 5, 3) a−→ (1, 5, 3, 4, 2) b−→ (2, 5, 4) a−→ (1, 5, 4, 3, 2)
c−1−→ (1, 2, 5, 4, 3) c
−1
−→ (3, 5, 4) a−→ (1, 2)(4, 5) b−→ (3, 4, 5) a−→ (1, 2)(3, 5)
b−→ e
4.18. A hamiltonian cycle in Cay(A5; a,b,c) with a = (1, 2)(3, 4), b = (1, 3)(2, 5), and c = (1, 2, 3).
e
a−→ (1, 2)(3, 4) b−→ (1, 4, 3, 2, 5) c
−1
−→ (1, 2, 4, 3, 5) a−→ (1, 4, 5)
b−→ (1, 3, 4, 5, 2) a−→ (2, 3, 5) b−→ (1, 5, 3) a−→ (1, 2, 5, 3, 4) c−→ (1, 5, 3, 2, 4)
b−→ (1, 2, 3, 5, 4) a−→ (1, 3)(4, 5) b−→ (2, 4, 5) a−→ (1, 4, 3, 5, 2) b−→ (1, 5)(3, 4)
a−→ (1, 2, 5) b−→ (1, 3, 2) a−→ (2, 3, 4) b−→ (1, 4, 2, 5, 3) c−→ (1, 5, 3, 4, 2)
a−→ (2, 5, 3) b−→ (1, 2, 3) a−→ (1, 3, 4) c
−1
−→ (1, 4)(2, 3) a−→ (1, 3)(2, 4)
b−→ (2, 5, 4) a−→ (1, 5, 4, 3, 2) c
−1
−→ (1, 2, 5, 4, 3) b−→ (2, 4, 3) a−→ (1, 4, 2)
b−→ (1, 3, 4, 2, 5) c−→ (1, 5)(2, 4) c−→ (1, 4, 2, 3, 5) a−→ (1, 3, 2, 4, 5) b−→ (1, 2)(4, 5)
a−→ (3, 5, 4) b−→ (1, 5, 2, 4, 3) a−→ (1, 4)(2, 5) c−→ (1, 5, 2, 3, 4) b−→ (1, 4)(3, 5)
a−→ (1, 2, 4, 5, 3) b−→ (2, 3)(4, 5) a−→ (1, 3, 5, 4, 2) c
−1
−→ (1, 5, 4, 2, 3) b−→ (2, 4)(3, 5)
a−→ (1, 4, 5, 3, 2) b−→ (1, 2, 3, 4, 5) a−→ (1, 3, 5) c
−1
−→ (1, 5)(2, 3) b−→ (1, 2)(3, 5)
a−→ (3, 4, 5) b−→ (1, 4, 5, 2, 3) a−→ (1, 3, 5, 2, 4) b−→ (1, 5, 4) c
−1
−→ (1, 3, 2, 5, 4)
b−→ (1, 2, 4) a−→ (1, 4, 3) b−→ (2, 5)(3, 4) a−→ (1, 5, 2) c
−1
−→ (1, 3)(2, 5)
b−→ e
References
[1] R. Gould, R. Roth, Cayley digraphs and (1,j,n)-sequencings of the alternating groups An, Discrete
Math. 66(1-2) (1987) 91–102.
29
http://dx.doi.org/10.1016/0012-365X(87)90121-X
http://dx.doi.org/10.1016/0012-365X(87)90121-X
D. W. Morris / J. Algebra Comb. Discrete Appl. 3(1) (2016) 13–30
[2] K. Kutnar, D. Marušič, D. W. Morris, J. Morris, P. Šparl, Hamiltonian cycles in Cayley graphs whose
order has few prime factors, Ars Math. Contemp. 5(1) (2012) 27–71.
[3] K. Kutnar, D. Marušič, D. W. Morris, J. Morris, P. Šparl, Cayley graphs on A5 are hamiltonian,
unpublished appendix to [2], http://arxiv.org/src/1009.5795/anc/A5.pdf.
[4] D. Witte, J. A. Gallian, A survey: Hamiltonian cycles in Cayley graphs, Discrete Math. 51(3) (1984)
293–304.
30
http://amc-journal.eu/index.php/amc/article/view/177/147
http://amc-journal.eu/index.php/amc/article/view/177/147
http://arxiv.org/src/1009.5795/anc/A5.pdf
http://arxiv.org/src/1009.5795/anc/A5.pdf
http://www.sciencedirect.com/science/article/pii/0012365X84900104
http://www.sciencedirect.com/science/article/pii/0012365X84900104
Introduction
Preliminaries
Proof of Proposition 1.2
Details of hamiltonian cycles in A5
References