# Cayley Graphs of Order27p Are Hamiltonian

Authors: Ebrahim Ghaderpour; Dave Witte Morris
Journal: International Journal of Combinatorics
 (2011)

---

## Abstract

Suppose thatG
is a finite group, such that |G|=27p, 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).


---

## Body

## 1. Introduction

Theorem 1.1.
If|G|=27p,  where p is prime, then every connected Cayley graph on G has a Hamiltonian cycle.Combining this with results in [1–3] establishes that (1.1)Every Cayley graph onGhas a hamiltonian cycleif|G|=kp,wherepis prime,1≤k<32,andk≠24.The remainder of the paper provides a proof of the theorem. Here is an outline. Section2 recalls known results on hamiltonian cycles in Cayley graphs; Section 3 presents the proof under the assumption that the Sylow p-subgroup of G is normal; Section 4 presents the proof under the assumption that the Sylow p-subgroups of G are not normal.


## 2. Preliminaries: Known Results on Hamiltonian Cycles in  Cayley Graphs

For convenience, we record some known results that provide hamiltonian cycles in various Cayley graphs, after fixing some notation.Notation 1 (see [4, Sections  1.1 and 5.1]).
For any groupG, we use the following notation: (1)
G′ denotes the commutator subgroup[G,G] of G,(2)
Z(G) denotes the center of G,(3)
Φ(G) denotes the Frattini subgroup of G.For a,b∈G, we use ab to denote the conjugateb-1ab.Notation 2.
If(s1,s2,…,sn)is any sequence, we use(s1,s2,…,sn)#to denote the sequence(s1,s2,…,sn-1)that is obtained by deleting the last term.Theorem 2.1 (Marušič, Durnberger, Keating-Witte [5]).
IfG′ is a cyclic group of prime-power order, then every connected Cayley graph on  G has a hamiltonian cycle.Lemma 2.2 (see [3, Lemma  2.27]).
LetS generate the finite group  G, and let  s∈S. If  (i)
〈s〉⊲G,(ii)
Cay(G/〈s〉;S) has a hamiltonian cycle, and(iii)
either
(1)
s∈Z(G), or(2)
|s| is prime,then Cay(G;S) has a hamiltonian cycle.Lemma 2.3 (see [1, Lemma  2.7]).
LetS generate the finite group  G, and let  s∈S. If  (i)
〈s〉⊲G,(ii)
|s| is a divisor of pq, where p and q are distinct primes,(iii)
sp∈Z(G),(iv)
|G/〈s〉| is divisible by q, and(v)
Cay(G/〈s〉;S) has a hamiltonian cycle,then there is a hamiltonian cycle in Cay(G;S).The following results are well known (and easy to prove).Lemma 2.4 (“Factor Group Lemma”).
Suppose that(i)
S is a generating set of G,(ii)
N is a cyclic, normal subgroup of G,(iii)
(s1N,…,snN) is a hamiltonian cycle in Cay(G/N;S), and(iv)
the products1s2⋯sn generates N.Then (s1,…,sn)|N| is a hamiltonian cycle in Cay(G;S).Corollary 2.5.
Suppose that(i)
S is a generating set of G,(ii)
N is a normal subgroup of G, such that |N| is prime,(iii)
s≡t(modN) for some s,t∈S∪S-1 with s≠t, and(iv)
there is a hamiltonian cycle inCay(G/N;S) that uses at least one edge labelled s.Then there is a hamiltonian cycle in Cay(G;S).Definition 2.6.
IfH is any subgroup of G, then H∖Cay(G;S) denotes the multigraph in which(i)
the vertices are the right cosets ofH, and(ii)
there is an edge joiningHg1 and Hg2 for each s∈S∪S-1, such that g1s∈Hg2.Thus, if there are two different elements s1 and s2 of S∪S-1, such that g1s1 and g1s2 are both in Hg2, then the vertices Hg1 and Hg2 are joined by a double edge.Lemma 2.7 (see [3, Corollary  2.9]).
Suppose that(i)
S is a generating set of G,(ii)
H is a subgroup of G, such that |H| is prime,(iii)
the quotient multigraphH∖Cay(G;S) has a hamiltonian cycle C, and(iv)
C uses some double-edge of H∖Cay(G;S).Then there is a hamiltonian cycle in Cay(G;S).Theorem 2.8 (see [6, Corollary  3.3]).
Suppose that(i)
S is a generating set of G,(ii)
N is a normal p-subgroup of G, and(iii)
st-1∈N, for all s,t∈S.Then Cay(G;S) has a hamiltonian cycle.Remark 2.9.
In the proof of our main result, we may assumep≥5, for otherwise either(i)
|G|=54 is of the form 18q, where q is prime, and so [3, Propostion  9.1] applies, or(ii)
|G|=34 is a prime power, and so the main theorem of [7] applies.


## 3. Assume the Sylowp-Subgroup of G Is Normal

Notation 3.
Let(i)
G be a group of order 27p, where p is prime, and p≥5(see Remark 2.9),(ii)
S be a minimal generating set for G,(iii)
P≅ℤp be a Sylow p-subgroup of G,(iv)
w be a generator of P, and(v)
Q be a Sylow 3-subgroup of G.Assumption 3.1.
In this section, we assume thatP is a normal subgroup of G.ThereforeG is a semidirect product: (3.1)G=Q⋉P.
We may assume that G′ is not cyclic of prime order (for otherwise Theorem 2.1 applies). This implies that Q is nonabelian and acts nontrivially on P; so (3.2)G′=Q′×Piscyclicoforder3p.Notation 4.
SinceQ is a 3-group and acts nontrivially on P≅ℤp, we must have p≡1(mod3). Thus, one may choose r∈ℤ, such that
(3.3)r3≡1(mod⁡p),butr≢1(mod⁡p).
Dividing r3-1 by r-1, we see that
(3.4)r2+r+1≡0(mod⁡p).


### 3.1. A Lemma That Applies to Both of the Possible Sylow 3-Subgroups

There are only 2 nonabelian groups of order 27, and we will consider them as separate cases, but, first, we cover some common ground.Note
SinceQis a nonabelian group of order
27,
andG=Q⋉P≅Q⋉ℤp, it is easy to see that(3.5)Q′=Φ(Q)=Z(Q)=Z(G)=Φ(G).Lemma 3.2.
Assume that(i)
s∈(S∪S-1)∩Q, such that s does not centralize P, and(ii)
c∈CQ(P)∖Φ(Q).Then we may assume that S is either {s,cw} or {s,c2w} or {s,scw} or {s,sc2w}.Proof.
SinceG/P≅Q is a 2-generated group of prime-power order, there must be an element a of S, such that {s,a} generates G/P. We may write
(3.6)a=sicjzwk,with0≤i≤2,1≤j≤2,z∈Z(Q),and0≤k<p.
Note the following. (i)
By replacinga with its inverse if necessary, we may assume i∈{0,1}.(ii)
By applying an automorphism ofG that fixes s and maps c to czj, we may assume that z is trivial (since (czj)j=cjzj2=cjz).(iii)
By replacingw with wk if k≠0, we may assume k∈{0,1}.Thus,
(3.7)a=sicjwkwithi,k∈{0,1},andj∈{1,2}.
Case 1 (Assumek=1).
Then〈s,a〉=G, and so S={s,a}. This yields the four listed generating sets.Case 2 (Assumek=0).
Then〈s,a〉=Q, and there must be a third element b of S, with b∉Q; after replacing w with an appropriate power, we may write b=tw with t∈Q. We must have t∈〈s,Φ(Q)〉, for otherwise 〈s,b〉=G (which contradicts the minimality of S). Therefore
(3.8)t=si′z′with0≤i′≤2,andz′∈Φ(Q)=Z(G).
We may assume the following.(i)
i′≠0, for otherwise b=z′w∈S∩(Z(G)×P); so Lemma 2.3 applies.(ii)
i′=1, by replacing b with its inverse if necessary.(iii)
z′≠e, for otherwise s and b provide a double edge in Cay(G/P;S); so Corollary 2.5 applies.Then s-1b=z′w generates Z(G)×P.
Consider the hamiltonian cycles(3.9)(a-1,s2)3,((a-1,s2)3#,b),((a-1,s2)3##,b2)
in Cay(G/〈z,w〉;S). Letting z′′=(a-1s2)3∈〈z〉, we see that their endpoints in G are (resp.)
(3.10)z′′,z′′(s-1b)=z′′z′w,z′′(s-1b)s(s-1b)=z′′(z′)2wsw.
The final two endpoints both have a nontrivial projection to P (since s, being a 3-element, cannot invert w), and at least one of these two endpoints also has a nontrivial projection to Z(G). Such an endpoint generates Z(G)×P=〈z,w〉, and so the Factor Group Lemma 2.4 provides a hamiltonian cycle in Cay(G;S).


### 3.2. Sylow 3-Subgroup of Exponent 3

Lemma 3.3.
Assume thatQ is of exponent  3; so
(3.11)Q=〈x,y,z∣x3=y3=z3=e,[x,y]=z,[x,z]=[y,z]=e〉.
Then one may assume the following: (1)
wx=wr, but y and z centralize P, and(2)
either
(a)
S={x,yw}, or(b)
S={x,xyw}.Proof.
(1)  SinceQ acts nontrivially on P, and Aut(P) is cyclic, but Q/Φ(Q) is not cyclic, there must be elements a and b of Q∖Φ(Q), such that a centralizes P, but b does not. (And z must centralize P, because it is in Q′.) By applying an automorphism of Q, we may assume a=y and b=x. Furthermore, we may assume wx=wr by replacing x with its inverse if necessary.
(2)S must contain an element that does not centralize P; so we may assume x∈S. By applying Lemma 3.2 with s=x and c=y, we see that we may assume that S is
(3.12){x,yw}or{x,y2w}or{x,xyw}or{x,xy2w}.
But there is an automorphism of G that fixes x and w and sends y to y2; so we need only consider two of these possibilities.Proposition 3.4.
Assume, as usual, that|G|=27p, where  p is prime, and that  G has a normal Sylow  p-subgroup. If the Sylow  3-subgroup  Q is of exponent  3, then  Cay(G;S) has a hamiltonian cycle.Proof.
We writeG¯ for the natural homomorphism from G to G¯=G/P. From Lemma 3.3(2), we see that we need only consider two possibilities for S.
Case 1 (AssumeS={x,yw}).
Fora=x and b=yw, we have the following hamiltonian cycle in Cay(G/P;S):
(3.13)e¯⟶ax¯⟶ax2¯⟶bx2y¯⟶a-1xyz¯⟶a-1yz2¯⟶by2z2¯⟶bz2¯⟶axz2¯⟶ax2z2¯⟶bx2yz2¯⟶ayz¯⟶axy¯⟶bxy2¯⟶ax2y2z¯⟶bx2z¯⟶bx2yz¯⟶a-1xyz2¯⟶bxy2z2¯⟶ax2y2¯⟶ay2z¯⟶bz¯⟶axz¯⟶b-1xy2z¯⟶ax2y2z2¯⟶ay2¯⟶b-1y¯⟶b-1e¯.
Its endpoint in G is
(3.14)a2ba-2b2a2ba2bab2a-1ba2bab-1a2b-2=x2ywx-2(yw)2x2ywx2ywx(yw)2x-1ywx2ywx(yw)-1x2(yw)-2=x2ywxy2w2x2ywx2ywxy2w2x2ywx2ywxy2w-1x2yw-2.
Since the walk is a hamiltonian cycle in G/P, we know that this endpoint is in P=〈w〉. So all terms except powers of w must cancel. Thus, we need only calculate the contribution from each appearance of w in this expression. To do this, note that if a term wi is followed by a net total of j appearances of x, then the term contributes a factor of wirj to the product. So the endpoint in G is
(3.15)wr13w2r12wr10wr8w2r7wr5wr3w-r2w-2.
Since r3≡1(modp), this simplifies to
(3.16)wrw2wrwr2w2rwr2ww-r2w-2=wr+2+r+r2+2r+r2+1-r2-2=wr2+4r+1=wr2+r+1w3r=w0w3r=w3r.
Since p∤3r, this endpoint generates P; so the Factor Group Lemma 2.4 provides a hamiltonian cycle in Cay(G;S).Case 2 (AssumeS={x,xyw}).
Fora=x and b=xyw, we have the hamiltonian cycle
(3.17)((a,b2)3#,a)3
in Cay(G/P;S). Its endpoint in G is
(3.18)((ab2)3b-1a)3=((x(xyw)2)3(xyw)-1x)3=((x(x2y2wr+1))3(w-1y-1x-1)x)3=((y2wr+1)3(w-1y-1))3=(w3(r+1)(w-1y-1))3=(y-1w3r+2)3=w3(3r+2).
Since we are free to choose r to be either of the two primitive cube roots of 1 in ℤp, and the equation 3r+2=0 has only one solution in ℤp, we may assume that r has been selected to make the exponent nonzero. Then the Factor Group Lemma 2.4 provides a hamiltonian cycle in Cay(G;S).


### 3.3. Sylow 3-Subgroup of Exponent 9

Lemma 3.5.
Assume thatQ is of exponent  9; so
(3.19)Q=〈x,y∣x9=y3=e,[x,y]=x3〉.
There are two possibilities for G, depending on whether CQ(P) contains an element of order 9 or not. (1)
Assume thatCQ(P) does not contain an element of order 9. Then we may assume that y centralizes P, but wx=wr. Furthermore, we may assume that:
(a)
S={x,yw}, or(b)
S={x,xyw}.(2)
Assume thatCQ(P) contains an element of order 9. Then we may assume x centralizes P, but wy=wr. Furthermore, we may assume that:
(a)
S={xw,y},(b)
S={xyw,y},(c)
S={xy,xw}, or(d)
S={xy,x2yw}.Proof.
(1) Sincex has order 9, we know that it does not centralize P. But x3 must centralize P (since x3 is in G′). Therefore, we may assume wx=xr (by replacing x with its inverse if necessary). Also, since Q/CQ(P) must be cyclic (because Aut(P) is cyclic), but CG(P) does not contain an element of order 9, we see that CQ(P) contains every element of order 3; so y must be in CQ(P).
SinceS must contain an element that does not centralize P, we may assume x∈S. By applying Lemma 3.2 with s=x and c=y, we see that we may assume that S is:
(3.20){x,yw}or{x,y2w}or{x,xyw}or{x,xy2w}.
The second generating set need not be considered, because (y2w)-1=yw-1=yw′; so it is equivalent to the first. Also, the fourth generating set can be converted into the third, since there is an automorphism of G that fixes y, but takes x to xyw and w to w-1.(2)
We may assumex∈CQ(P); so CQ(P)=〈x〉.
We know thatS must contain an element s that does not centralize P, and there are two possibilities: either (I)
s has order 3, or(II)
s has order 9.We consider these two possibilities as separate cases.
Case I (Assume thatshas order3).
We may assumes=y. Letting c=x, we see from Lemma 3.2 that we may assume S is either
(3.21){y,xw}or{y,x2w}or{y,yxw}or{y,yx2w}.
The second and fourth generating sets need not be considered, because there is an automorphism of G that fixes y and w, but takes x to x2. Also, the third generating set may be replaced with {y,xyw}, since there is an automorphism of G that fixes y and w, but takes x to y-1xy.Case II (Assume thatshas order9).
We may assumes=xy. Letting c=x, we see from Lemma 3.2 that we may assume that S is either
(3.22){xy,xw}or{xy,x2w}or{xy,xyxw}or{xy,xyx2w}.
The second generating set is equivalent to {xy,xw}, since the automorphism of G that sends x to x4, y to x-3y, and w to w-1 maps it to {xy,(xw)-1}. The third generating set is mapped to {xy,x2yw} by the automorphism that sends x to x[x,y] and y to [x,y]-1y. The fourth generating set need not be considered, because xyx2w is an element of order 3 that does not centralize P, which puts it in the previous case.Proposition 3.6.
Assume, as usual, that|G|=27p, where  p is prime, and that  G has a normal Sylow  p-subgroup. If the Sylow  3-subgroup  Q is of exponent  9, then  Cay(G;S) has a hamiltonian cycle.Proof.
We will show that, for an appropriate choice ofa and b in S∪S-1, the walk
(3.23)(a3,b-1,a,b-1,a4,b2,a-2,b,a2,b,a3,b,a-1,b-1,a-1,b-2)
provides a hamiltonian cycle in Cay(G/P;S) whose endpoint in G generates P (so the Factor Group Lemma 2.4 applies).
We begin by verifying two situations in which (3.23) is a hamiltonian cycle.(HC1)
If|a¯|=9, |b¯|=3, and ab¯=a4¯ in G¯=G/P, then we have the hamiltonian cycle:(3.24)e¯⟶aa¯⟶aa2¯⟶aa3¯⟶b-1a3b2¯⟶aa7b2¯⟶b-1a7b¯⟶aa5b¯⟶aa3b¯⟶aab¯⟶aa8b¯⟶ba8b2¯⟶ba8¯⟶a-1a7¯⟶a-1a6¯⟶ba6b¯⟶aa4b¯⟶aa2b¯⟶ba2b2¯⟶aa6b2¯⟶aab2¯⟶aa5b2¯⟶ba5¯⟶a-1a4¯⟶b-1a4b2¯⟶a-1b2¯⟶b-1b¯⟶b-1e¯.(HC2)
If|a¯|=9, |b¯|=9, ab¯=a7¯, and b3¯=a6¯ in G¯=G/P, then we have the hamiltonian cycle:(3.25)e¯⟶aa¯⟶aa2¯⟶aa3¯⟶b-1a6b2¯⟶aa4b2¯⟶b-1a4b¯⟶aa8b¯⟶aa3b¯⟶aa7b¯⟶aa2b¯⟶ba2b2¯⟶ba8¯⟶a-1a7¯⟶a-1a6¯⟶ba6b¯⟶aab¯⟶aa5b¯⟶ba5b2¯⟶aa3b2¯⟶aab2¯⟶aa8b2¯⟶ba5¯⟶a-1a4¯⟶b-1a7b2¯⟶a-1b2¯⟶b-1b¯⟶b-1e¯.
To calculate the endpoint inG, fix r1,r2∈ℤp, with
(3.26)wa=wr1,wb=wr2,
and write
(3.27)a=a̲w1,b=b̲w2,wherea̲,b̲∈Q,w1,w2∈P.
Note that if an occurrence of wi in the product is followed by a net total of j1 appearances of a̲ and a net total of j2 appearances of b̲, then it contributes a factor of wir1j1r2j2 to the product. (A similar occurrence of wi-1 contributes a factor of wi-r1j1r2j2 to the product.) Furthermore, since r13≡r23≡1(modp), there is no harm in reducing j1 and j2 modulo 3.
We will apply these considerations only in a few particular situations.(E1)
Assumew1=e (so a∈Q and a̲=a). Then the endpoint of the path in G is
(3.28)a3b-1ab-1a4b2a-2ba2ba3ba-1b-1a-1b-2=a3(b̲w2)-1a(b̲w2)-1a4(b̲w2)2a-2(b̲w2)a2×(b̲w2)a3(b̲w2)a-1(b̲w2)-1a-1(b̲w2)-2=a3(w2-1b̲-1)a(w2-1b̲-1)a4(b̲w2b̲w2)a-2(b̲w2)a2×(b̲w2)a3(b̲w2)a-1(w2-1b̲-1)a-1(w2-1b̲-1w2-1b̲-1).
By the above considerations, this simplifies to w2m, where
(3.29)m=-1-r12r2+r1r2+r1+r22+r1r2+r1-r12-r2-r22=-r12r2-r12+2r1r2+2r1-r2-1.
Note the following.
(a)
Ifr1≠1 and r2=1, then m simplifies to 6r1, because r12+r1+1≡0(modp) in this case.(b)
Ifr1≠1 and r2≠1, then m simplifies to 3r1(r2+1), because r12+r1+1≡r22+r2+1≡0(modp) in this case.(E2)
Assumew2=e (so b∈Q and b̲=b). Then the endpoint of the path in G is
(3.30)a3b-1ab-1a4b2a-2ba2ba3ba-1b-1a-1b-2=(a̲w1)3b-1(a̲w1)b-1(a̲w1)4b2(a̲w1)-2b(a̲w1)2b(a̲w1)3b(a̲w1)-1b-1(a̲w1)-1b-2=(a̲w1a̲w1a̲w1)b-1(a̲w1)b-1(a̲w1a̲w1a̲w1a̲w1)b2(w1-1a̲-1w1-1a̲-1)×b(a̲w1a̲w1)b(a̲w1a̲w1a̲w1)b(w1-1a̲-1)b-1(w1-1a̲-1)b-2.
By the above considerations, this simplifies to w1m, where
(3.31)m=r12+r1+1+r12r2+r1r22+r22+r12r22+r1r22-r1-r12+r12r22+r1r22+r2+r12r2+r1r2-r1-r12r2=2r12r22+3r1r22+r22+r12r2+r1r2+r2-r1+1.
Note the following.
(a)
Ifr1=1 and r2≠1, then m simplifies to -3(r2+2), because r22+r2+1≡0(modp) in this case.(b)
Ifr1≠1 and r2≠1, then m simplifies to -r1r2-2r1+r2+2, because r12+r1+1≡r22+r2+1≡0(modp) in this case.
Now we provide a hamiltonian cycle for each of the generating sets listed in Lemma3.5. (1a)
IfCQ(P) has exponent 3, and S={x,yw}, we let a=x and b=yw in (HC1). In this case, we have w1=e, r1=r, and r2=1; so (E1(a)) tells us that the endpoint in G is w26r.(1b)
IfCQ(P) has exponent 3, and S={x,xyw}, we let a=x and b=(xyw)-1 in (HC2). In this case, we have w1=e, r1=r, and r2=r-1=r2; so (E1(b)) tells us that the endpoint in G is w2m, where
(3.32)m=3r1(r2+1)=3r(r2+1)=3(r3+r)≡3(1+r)=3(r+1)(mod⁡p).(2a)
IfCQ(P) has exponent 9, and S={xw,y}, we let a=xw and b=y in (HC1). In this case, we have w2=e, r1=1, and r2=r; so (E2(a)) tells us that the endpoint in G is w1-3(r+2).(2b)
IfCQ(P) has exponent 9, and S={xyw,y}, we let a=xyw and b=y in (HC1). In this case, we have w2=e and r1=r2=r; so (E2(b)) tells us that the endpoint in G is w2m, where
(3.33)m=-r1r2-2r1+r2+2=-r2-2r+r+2=-(r2+r+1)+3≡3(mod⁡p).(2c)
IfCQ(P) has exponent 9, and S={xy,xw}, we let a=xw and b=(xy)-1 in (HC2). In this case, we have w2=e, r1=1, and r2=r-1=r2; so (E2(a)) tells us that the endpoint in G is w1m, where
(3.34)m=-3(r2+2)=-3(r2+2)≡-3(-(r+1)+2)=3(r-1)(mod⁡p).(2d)
IfCQ(P) has exponent 9, and S={xy,x2yw}, we let a=xy and b=x2yw in (HC2). In this case, we have w1=e and r1=r2=r; so (E1(b)) tells us that the endpoint in G is w2m, where
(3.35)m=3r1(r2+1)=3r(r+1)=3(r2+r)≡3(-1)=-3(mod⁡p). In all cases, there is at most one nonzero value of r (modulo p) for which the exponent of wi is 0. Since we are free to choose r to be either of the two primitive cube roots of 1 in ℤp, we may assume that r has been selected to make the exponent nonzero. Then the Factor Group Lemma 2.4 provides a hamiltonian cycle in Cay(G;S).


## 3.1. A Lemma That Applies to Both of the Possible Sylow 3-Subgroups

There are only 2 nonabelian groups of order 27, and we will consider them as separate cases, but, first, we cover some common ground.Note
SinceQis a nonabelian group of order
27,
andG=Q⋉P≅Q⋉ℤp, it is easy to see that(3.5)Q′=Φ(Q)=Z(Q)=Z(G)=Φ(G).Lemma 3.2.
Assume that(i)
s∈(S∪S-1)∩Q, such that s does not centralize P, and(ii)
c∈CQ(P)∖Φ(Q).Then we may assume that S is either {s,cw} or {s,c2w} or {s,scw} or {s,sc2w}.Proof.
SinceG/P≅Q is a 2-generated group of prime-power order, there must be an element a of S, such that {s,a} generates G/P. We may write
(3.6)a=sicjzwk,with0≤i≤2,1≤j≤2,z∈Z(Q),and0≤k<p.
Note the following. (i)
By replacinga with its inverse if necessary, we may assume i∈{0,1}.(ii)
By applying an automorphism ofG that fixes s and maps c to czj, we may assume that z is trivial (since (czj)j=cjzj2=cjz).(iii)
By replacingw with wk if k≠0, we may assume k∈{0,1}.Thus,
(3.7)a=sicjwkwithi,k∈{0,1},andj∈{1,2}.
Case 1 (Assumek=1).
Then〈s,a〉=G, and so S={s,a}. This yields the four listed generating sets.Case 2 (Assumek=0).
Then〈s,a〉=Q, and there must be a third element b of S, with b∉Q; after replacing w with an appropriate power, we may write b=tw with t∈Q. We must have t∈〈s,Φ(Q)〉, for otherwise 〈s,b〉=G (which contradicts the minimality of S). Therefore
(3.8)t=si′z′with0≤i′≤2,andz′∈Φ(Q)=Z(G).
We may assume the following.(i)
i′≠0, for otherwise b=z′w∈S∩(Z(G)×P); so Lemma 2.3 applies.(ii)
i′=1, by replacing b with its inverse if necessary.(iii)
z′≠e, for otherwise s and b provide a double edge in Cay(G/P;S); so Corollary 2.5 applies.Then s-1b=z′w generates Z(G)×P.
Consider the hamiltonian cycles(3.9)(a-1,s2)3,((a-1,s2)3#,b),((a-1,s2)3##,b2)
in Cay(G/〈z,w〉;S). Letting z′′=(a-1s2)3∈〈z〉, we see that their endpoints in G are (resp.)
(3.10)z′′,z′′(s-1b)=z′′z′w,z′′(s-1b)s(s-1b)=z′′(z′)2wsw.
The final two endpoints both have a nontrivial projection to P (since s, being a 3-element, cannot invert w), and at least one of these two endpoints also has a nontrivial projection to Z(G). Such an endpoint generates Z(G)×P=〈z,w〉, and so the Factor Group Lemma 2.4 provides a hamiltonian cycle in Cay(G;S).


## 3.2. Sylow 3-Subgroup of Exponent 3

Lemma 3.3.
Assume thatQ is of exponent  3; so
(3.11)Q=〈x,y,z∣x3=y3=z3=e,[x,y]=z,[x,z]=[y,z]=e〉.
Then one may assume the following: (1)
wx=wr, but y and z centralize P, and(2)
either
(a)
S={x,yw}, or(b)
S={x,xyw}.Proof.
(1)  SinceQ acts nontrivially on P, and Aut(P) is cyclic, but Q/Φ(Q) is not cyclic, there must be elements a and b of Q∖Φ(Q), such that a centralizes P, but b does not. (And z must centralize P, because it is in Q′.) By applying an automorphism of Q, we may assume a=y and b=x. Furthermore, we may assume wx=wr by replacing x with its inverse if necessary.
(2)S must contain an element that does not centralize P; so we may assume x∈S. By applying Lemma 3.2 with s=x and c=y, we see that we may assume that S is
(3.12){x,yw}or{x,y2w}or{x,xyw}or{x,xy2w}.
But there is an automorphism of G that fixes x and w and sends y to y2; so we need only consider two of these possibilities.Proposition 3.4.
Assume, as usual, that|G|=27p, where  p is prime, and that  G has a normal Sylow  p-subgroup. If the Sylow  3-subgroup  Q is of exponent  3, then  Cay(G;S) has a hamiltonian cycle.Proof.
We writeG¯ for the natural homomorphism from G to G¯=G/P. From Lemma 3.3(2), we see that we need only consider two possibilities for S.
Case 1 (AssumeS={x,yw}).
Fora=x and b=yw, we have the following hamiltonian cycle in Cay(G/P;S):
(3.13)e¯⟶ax¯⟶ax2¯⟶bx2y¯⟶a-1xyz¯⟶a-1yz2¯⟶by2z2¯⟶bz2¯⟶axz2¯⟶ax2z2¯⟶bx2yz2¯⟶ayz¯⟶axy¯⟶bxy2¯⟶ax2y2z¯⟶bx2z¯⟶bx2yz¯⟶a-1xyz2¯⟶bxy2z2¯⟶ax2y2¯⟶ay2z¯⟶bz¯⟶axz¯⟶b-1xy2z¯⟶ax2y2z2¯⟶ay2¯⟶b-1y¯⟶b-1e¯.
Its endpoint in G is
(3.14)a2ba-2b2a2ba2bab2a-1ba2bab-1a2b-2=x2ywx-2(yw)2x2ywx2ywx(yw)2x-1ywx2ywx(yw)-1x2(yw)-2=x2ywxy2w2x2ywx2ywxy2w2x2ywx2ywxy2w-1x2yw-2.
Since the walk is a hamiltonian cycle in G/P, we know that this endpoint is in P=〈w〉. So all terms except powers of w must cancel. Thus, we need only calculate the contribution from each appearance of w in this expression. To do this, note that if a term wi is followed by a net total of j appearances of x, then the term contributes a factor of wirj to the product. So the endpoint in G is
(3.15)wr13w2r12wr10wr8w2r7wr5wr3w-r2w-2.
Since r3≡1(modp), this simplifies to
(3.16)wrw2wrwr2w2rwr2ww-r2w-2=wr+2+r+r2+2r+r2+1-r2-2=wr2+4r+1=wr2+r+1w3r=w0w3r=w3r.
Since p∤3r, this endpoint generates P; so the Factor Group Lemma 2.4 provides a hamiltonian cycle in Cay(G;S).Case 2 (AssumeS={x,xyw}).
Fora=x and b=xyw, we have the hamiltonian cycle
(3.17)((a,b2)3#,a)3
in Cay(G/P;S). Its endpoint in G is
(3.18)((ab2)3b-1a)3=((x(xyw)2)3(xyw)-1x)3=((x(x2y2wr+1))3(w-1y-1x-1)x)3=((y2wr+1)3(w-1y-1))3=(w3(r+1)(w-1y-1))3=(y-1w3r+2)3=w3(3r+2).
Since we are free to choose r to be either of the two primitive cube roots of 1 in ℤp, and the equation 3r+2=0 has only one solution in ℤp, we may assume that r has been selected to make the exponent nonzero. Then the Factor Group Lemma 2.4 provides a hamiltonian cycle in Cay(G;S).


## 3.3. Sylow 3-Subgroup of Exponent 9

Lemma 3.5.
Assume thatQ is of exponent  9; so
(3.19)Q=〈x,y∣x9=y3=e,[x,y]=x3〉.
There are two possibilities for G, depending on whether CQ(P) contains an element of order 9 or not. (1)
Assume thatCQ(P) does not contain an element of order 9. Then we may assume that y centralizes P, but wx=wr. Furthermore, we may assume that:
(a)
S={x,yw}, or(b)
S={x,xyw}.(2)
Assume thatCQ(P) contains an element of order 9. Then we may assume x centralizes P, but wy=wr. Furthermore, we may assume that:
(a)
S={xw,y},(b)
S={xyw,y},(c)
S={xy,xw}, or(d)
S={xy,x2yw}.Proof.
(1) Sincex has order 9, we know that it does not centralize P. But x3 must centralize P (since x3 is in G′). Therefore, we may assume wx=xr (by replacing x with its inverse if necessary). Also, since Q/CQ(P) must be cyclic (because Aut(P) is cyclic), but CG(P) does not contain an element of order 9, we see that CQ(P) contains every element of order 3; so y must be in CQ(P).
SinceS must contain an element that does not centralize P, we may assume x∈S. By applying Lemma 3.2 with s=x and c=y, we see that we may assume that S is:
(3.20){x,yw}or{x,y2w}or{x,xyw}or{x,xy2w}.
The second generating set need not be considered, because (y2w)-1=yw-1=yw′; so it is equivalent to the first. Also, the fourth generating set can be converted into the third, since there is an automorphism of G that fixes y, but takes x to xyw and w to w-1.(2)
We may assumex∈CQ(P); so CQ(P)=〈x〉.
We know thatS must contain an element s that does not centralize P, and there are two possibilities: either (I)
s has order 3, or(II)
s has order 9.We consider these two possibilities as separate cases.
Case I (Assume thatshas order3).
We may assumes=y. Letting c=x, we see from Lemma 3.2 that we may assume S is either
(3.21){y,xw}or{y,x2w}or{y,yxw}or{y,yx2w}.
The second and fourth generating sets need not be considered, because there is an automorphism of G that fixes y and w, but takes x to x2. Also, the third generating set may be replaced with {y,xyw}, since there is an automorphism of G that fixes y and w, but takes x to y-1xy.Case II (Assume thatshas order9).
We may assumes=xy. Letting c=x, we see from Lemma 3.2 that we may assume that S is either
(3.22){xy,xw}or{xy,x2w}or{xy,xyxw}or{xy,xyx2w}.
The second generating set is equivalent to {xy,xw}, since the automorphism of G that sends x to x4, y to x-3y, and w to w-1 maps it to {xy,(xw)-1}. The third generating set is mapped to {xy,x2yw} by the automorphism that sends x to x[x,y] and y to [x,y]-1y. The fourth generating set need not be considered, because xyx2w is an element of order 3 that does not centralize P, which puts it in the previous case.Proposition 3.6.
Assume, as usual, that|G|=27p, where  p is prime, and that  G has a normal Sylow  p-subgroup. If the Sylow  3-subgroup  Q is of exponent  9, then  Cay(G;S) has a hamiltonian cycle.Proof.
We will show that, for an appropriate choice ofa and b in S∪S-1, the walk
(3.23)(a3,b-1,a,b-1,a4,b2,a-2,b,a2,b,a3,b,a-1,b-1,a-1,b-2)
provides a hamiltonian cycle in Cay(G/P;S) whose endpoint in G generates P (so the Factor Group Lemma 2.4 applies).
We begin by verifying two situations in which (3.23) is a hamiltonian cycle.(HC1)
If|a¯|=9, |b¯|=3, and ab¯=a4¯ in G¯=G/P, then we have the hamiltonian cycle:(3.24)e¯⟶aa¯⟶aa2¯⟶aa3¯⟶b-1a3b2¯⟶aa7b2¯⟶b-1a7b¯⟶aa5b¯⟶aa3b¯⟶aab¯⟶aa8b¯⟶ba8b2¯⟶ba8¯⟶a-1a7¯⟶a-1a6¯⟶ba6b¯⟶aa4b¯⟶aa2b¯⟶ba2b2¯⟶aa6b2¯⟶aab2¯⟶aa5b2¯⟶ba5¯⟶a-1a4¯⟶b-1a4b2¯⟶a-1b2¯⟶b-1b¯⟶b-1e¯.(HC2)
If|a¯|=9, |b¯|=9, ab¯=a7¯, and b3¯=a6¯ in G¯=G/P, then we have the hamiltonian cycle:(3.25)e¯⟶aa¯⟶aa2¯⟶aa3¯⟶b-1a6b2¯⟶aa4b2¯⟶b-1a4b¯⟶aa8b¯⟶aa3b¯⟶aa7b¯⟶aa2b¯⟶ba2b2¯⟶ba8¯⟶a-1a7¯⟶a-1a6¯⟶ba6b¯⟶aab¯⟶aa5b¯⟶ba5b2¯⟶aa3b2¯⟶aab2¯⟶aa8b2¯⟶ba5¯⟶a-1a4¯⟶b-1a7b2¯⟶a-1b2¯⟶b-1b¯⟶b-1e¯.
To calculate the endpoint inG, fix r1,r2∈ℤp, with
(3.26)wa=wr1,wb=wr2,
and write
(3.27)a=a̲w1,b=b̲w2,wherea̲,b̲∈Q,w1,w2∈P.
Note that if an occurrence of wi in the product is followed by a net total of j1 appearances of a̲ and a net total of j2 appearances of b̲, then it contributes a factor of wir1j1r2j2 to the product. (A similar occurrence of wi-1 contributes a factor of wi-r1j1r2j2 to the product.) Furthermore, since r13≡r23≡1(modp), there is no harm in reducing j1 and j2 modulo 3.
We will apply these considerations only in a few particular situations.(E1)
Assumew1=e (so a∈Q and a̲=a). Then the endpoint of the path in G is
(3.28)a3b-1ab-1a4b2a-2ba2ba3ba-1b-1a-1b-2=a3(b̲w2)-1a(b̲w2)-1a4(b̲w2)2a-2(b̲w2)a2×(b̲w2)a3(b̲w2)a-1(b̲w2)-1a-1(b̲w2)-2=a3(w2-1b̲-1)a(w2-1b̲-1)a4(b̲w2b̲w2)a-2(b̲w2)a2×(b̲w2)a3(b̲w2)a-1(w2-1b̲-1)a-1(w2-1b̲-1w2-1b̲-1).
By the above considerations, this simplifies to w2m, where
(3.29)m=-1-r12r2+r1r2+r1+r22+r1r2+r1-r12-r2-r22=-r12r2-r12+2r1r2+2r1-r2-1.
Note the following.
(a)
Ifr1≠1 and r2=1, then m simplifies to 6r1, because r12+r1+1≡0(modp) in this case.(b)
Ifr1≠1 and r2≠1, then m simplifies to 3r1(r2+1), because r12+r1+1≡r22+r2+1≡0(modp) in this case.(E2)
Assumew2=e (so b∈Q and b̲=b). Then the endpoint of the path in G is
(3.30)a3b-1ab-1a4b2a-2ba2ba3ba-1b-1a-1b-2=(a̲w1)3b-1(a̲w1)b-1(a̲w1)4b2(a̲w1)-2b(a̲w1)2b(a̲w1)3b(a̲w1)-1b-1(a̲w1)-1b-2=(a̲w1a̲w1a̲w1)b-1(a̲w1)b-1(a̲w1a̲w1a̲w1a̲w1)b2(w1-1a̲-1w1-1a̲-1)×b(a̲w1a̲w1)b(a̲w1a̲w1a̲w1)b(w1-1a̲-1)b-1(w1-1a̲-1)b-2.
By the above considerations, this simplifies to w1m, where
(3.31)m=r12+r1+1+r12r2+r1r22+r22+r12r22+r1r22-r1-r12+r12r22+r1r22+r2+r12r2+r1r2-r1-r12r2=2r12r22+3r1r22+r22+r12r2+r1r2+r2-r1+1.
Note the following.
(a)
Ifr1=1 and r2≠1, then m simplifies to -3(r2+2), because r22+r2+1≡0(modp) in this case.(b)
Ifr1≠1 and r2≠1, then m simplifies to -r1r2-2r1+r2+2, because r12+r1+1≡r22+r2+1≡0(modp) in this case.
Now we provide a hamiltonian cycle for each of the generating sets listed in Lemma3.5. (1a)
IfCQ(P) has exponent 3, and S={x,yw}, we let a=x and b=yw in (HC1). In this case, we have w1=e, r1=r, and r2=1; so (E1(a)) tells us that the endpoint in G is w26r.(1b)
IfCQ(P) has exponent 3, and S={x,xyw}, we let a=x and b=(xyw)-1 in (HC2). In this case, we have w1=e, r1=r, and r2=r-1=r2; so (E1(b)) tells us that the endpoint in G is w2m, where
(3.32)m=3r1(r2+1)=3r(r2+1)=3(r3+r)≡3(1+r)=3(r+1)(mod⁡p).(2a)
IfCQ(P) has exponent 9, and S={xw,y}, we let a=xw and b=y in (HC1). In this case, we have w2=e, r1=1, and r2=r; so (E2(a)) tells us that the endpoint in G is w1-3(r+2).(2b)
IfCQ(P) has exponent 9, and S={xyw,y}, we let a=xyw and b=y in (HC1). In this case, we have w2=e and r1=r2=r; so (E2(b)) tells us that the endpoint in G is w2m, where
(3.33)m=-r1r2-2r1+r2+2=-r2-2r+r+2=-(r2+r+1)+3≡3(mod⁡p).(2c)
IfCQ(P) has exponent 9, and S={xy,xw}, we let a=xw and b=(xy)-1 in (HC2). In this case, we have w2=e, r1=1, and r2=r-1=r2; so (E2(a)) tells us that the endpoint in G is w1m, where
(3.34)m=-3(r2+2)=-3(r2+2)≡-3(-(r+1)+2)=3(r-1)(mod⁡p).(2d)
IfCQ(P) has exponent 9, and S={xy,x2yw}, we let a=xy and b=x2yw in (HC2). In this case, we have w1=e and r1=r2=r; so (E1(b)) tells us that the endpoint in G is w2m, where
(3.35)m=3r1(r2+1)=3r(r+1)=3(r2+r)≡3(-1)=-3(mod⁡p). In all cases, there is at most one nonzero value of r (modulo p) for which the exponent of wi is 0. Since we are free to choose r to be either of the two primitive cube roots of 1 in ℤp, we may assume that r has been selected to make the exponent nonzero. Then the Factor Group Lemma 2.4 provides a hamiltonian cycle in Cay(G;S).


## 4. Assume the Sylowp-Subgroups of G Are Not Normal

Lemma 4.1.
Assume that(i)
|G|=27p, where p is an odd prime, and(ii)
the Sylowp-subgroups of G are not normal.Then p=13, and G=ℤ13⋉(ℤ3)3, where a generator w of ℤ13 acts on (ℤ3)3 via multiplication on the right by the matrix
(4.1)W=[010001110].
Furthermore, we may assume that
(4.2)Sisoftheform{wi,wjv},
where v=(1,0,0)∈(ℤ3)3, and
(4.3)(i,j)∈{(1,0),(2,0),(1,2),(1,3),(1,5),(1,6),(2,5)}.Proof.
LetP be a Sylow p-subgroup of G, and let Q be a Sylow 3-subgroup of G. Since no odd prime divides 3-1 or 32-1, and 13 is the only odd prime that divides 33-1, Sylow's Theorem [8, Theorem  15.7, page  230] implies that p=13, and that NG(P)=P; so G must have a normal p-complement [4, Theorem  7.4.3]; that is, G=P⋉Q. Since P must act nontrivially on Q (since P is not normal), we know that it must act nontrivially on Q/Φ(Q) [4, Theorem  5.3.5, page  180]. However, P cannot act nontrivially on an elementary abelian group of order 3 or 32, because |P|=13 is not a divisor of 3-1 or 32-1. Therefore, we must have |Q/Φ(Q)|=33; so Q must be elementary abelian (and the action of P is irreducible).
LetW be the matrix representing the action of w on (ℤ3)3 (with respect to some basis that will be specified later). In the polynomial ring ℤ3[X], we have the factorization:
(4.4)X13-1X-1=(X3-X-1)⋅(X3+X2-1)⋅(X3+X2+X-1)⋅(X3-X2-X-1).
Since w13=e, the minimal polynomial of W must be one of the factors on the right-hand side. By replacing w with an appropriate power, we may assume that it is the first factor. Then, choosing any nonzero v∈(ℤ3)3, the matrix representation of w with respect to the basis {v,vw,vw2} is W (the Rational Canonical Form).
Now, letζ be a primitive 13th root of unity in the finite field GF(27). Then any Galois automorphism of GF(27) over GF(3) must raise ζ to a power. Since the subgroup of order 3 in ℤ13× is generated by the number 3, we conclude that the orbit of ζ under the Galois group is {ζ,ζ3,ζ9}. These must be the 3 roots of one of the irreducible factors on the right-hand side of (4.4). Thus, for any k∈ℤ13×, the matrices Wk, W3k, and W9k all have the same minimal polynomial; so they are conjugate under GL3(3). That is,
(4.5)powersofWinthesamerowofthefollowingarrayareconjugateunderGL3(3):W,W3,W9W2,W5,W6W4,W12,W10W7,W8,W11.
There is an elementa of S that generates G/Q≅P. Then a has order p; so, replacing it by a conjugate, we may assume a∈P=〈w〉, and so a=wi for some i∈ℤ13×. From (4.5), we see that we may assume i∈{1,2} (perhaps after replacing a by its inverse).
Now letb be the second element of S; so we may assume b=wjv for some j. We may assume 0≤j≤6 (by replacing b with its inverse, if necessary). We may also assume j≠i, for otherwise S⊂aQ, and so Theorem 2.8 applies.
Ifj=0, then (i,j) is either (1,0) or (2,0), both of which appear in the list; henceforth, let us assume j≠0.
Case 1 (Assumei=1).
Sincej≠i, we must have j∈{2,3,4,5,6}.
Note that sinceW3 is conjugate to W under GL3(3) (since they are in the same row of (4.5)), we know that the pair (w,w4) is isomorphic to the pair (w3,(w3)4)=(w3,w-1). By replacing b with its inverse, and then interchanging a and b, this is transformed to (w,w3). So we may assume j≠4.Case 2 (Assumei=2).
We may assume thatWj is in the second or fourth row of the table (for otherwise we could interchange a with b to enter the previous case. So j∈{2,5,6}. Since j≠i, this implies j∈{5,6}. However, since W5 is conjugate to W2 (since they are in the same row of (4.5)), and we have (w2)3=w6 and (w5)3=w2, we see that the pair (w2,w6) is isomorphic to (w2,w5). So we may assume j≠6.Proposition 4.2.
If|G|=27p, where  p is prime, and the Sylow  p-subgroups of  G are not normal, then  Cay(G;S) has a hamiltonian cycle.Proof.
From Lemma4.1 (and Remark 2.9), we may assume G=ℤ13⋉(ℤ3)3. For each of the generating sets listed in Lemma 4.1, we provide an explicit hamiltonian cycle in the quotient multigraph P∖Cay(G;S) that uses at least one double edge. So Lemma 2.7 applies.
To save space, we usei1i2i3 to denote the vertex P(i1,i2,i3).(i,j)=(1,0)a=w,a-1=w12,b=(1,0,0),andb-1=(-1,0,0)Double edge: 222→022witha-1and b:(4.6)000⟶b-1200⟶a020⟶a002⟶a220⟶b-1120⟶a012⟶a221⟶a102⟶b202⟶a210⟶a021⟶a112⟶a201⟶b-1101⟶a-1211⟶a-1212⟶a-1222⟶b022⟶b122⟶a-1121⟶a-1111⟶b-1011⟶a-1110⟶a-1001⟶a-1010⟶a-1100⟶b-1000.(i,j)=(2,0)a=w2,a-1=w11,b=(1,0,0),andb-1=(-1,0,0)Double edge: 020→220withaandb-1:(4.7)000⟶b-1200⟶a002⟶a022⟶a212⟶b-1112⟶a-1210⟶a-1122⟶a-1111⟶a-1110⟶b-1010⟶a-1201⟶b-1101⟶a012⟶a102⟶a020⟶b-1220⟶a222⟶a211⟶a120⟶a221⟶b021⟶a-1202⟶a-1121⟶a-1011⟶a-1001⟶a-1100⟶b-1000.(i,j)=(1,2)a=w,a-1=w12,b=w2(1,0,0),andb-1=w11(-1,-1,1)Double edge: 220→022withaandb:(4.8)000⟶b-1221⟶a-1012⟶a-1120⟶b-1102⟶b-1200⟶a020⟶a002⟶a220⟶b022⟶a222⟶b011⟶a111⟶a121⟶a122⟶a202⟶a210⟶a021⟶a112⟶b-1101⟶a-1211⟶a-1212⟶b201⟶b110⟶a-1001⟶a-1010⟶a-1100⟶b-1000.(i,j)=(1,3)a=w,a-1=w12,b=w3(1,0,0),andb-1=w10(0,1,-1)Double edge:200→020 with a and b:(4.9)000⟶b-1012⟶a-1120⟶b-1221⟶a102⟶a200⟶b020⟶a002⟶a220⟶a022⟶a222⟶a212⟶a211⟶a101⟶b-1201⟶a-1112⟶a-1021⟶a-1210⟶a-1202⟶a-1122⟶b121⟶a-1111⟶a-1011⟶a-1110⟶a-1001⟶a-1010⟶a-1100⟶b-1000.(i,j)=(1,5)a=w,a-1=w12,b=w5(1,0,0),andb-1=w8(1,0,1)Double edge: 220→022 with a and b-1:(4.10)000⟶b-1101⟶a120⟶a012⟶a221⟶b-1010⟶a001⟶a110⟶a011⟶a111⟶b121⟶a122⟶b-1102⟶a200⟶a020⟶a002⟶a220⟶b-1022⟶a222⟶a212⟶a211⟶b202⟶a210⟶a021⟶a112⟶a201⟶a100⟶b-1000.(i,j)=(1,6)a=w,a-1=w12,b=w6(1,0,0),andb-1=w7(-1,1,1)Double edge: 021→210witha-1 and b:(4.11)000⟶b-1211⟶b-1201⟶a-1112⟶a-1021⟶b210⟶b101⟶b120⟶a012⟶a221⟶a102⟶a200⟶a020⟶a002⟶a220⟶a022⟶a222⟶a212⟶b202⟶a-1122⟶a-1121⟶a-1111⟶a-1011⟶a-1110⟶a-1001⟶a-1010⟶a-1100⟶b-1000.(i,j)=(2,5)a=w2,a-1=w11,b=w5(1,0,0),andb-1=w8(1,0,1)Double edge:112→210witha-1andb:(4.12)000⟶b-1101⟶a012⟶b102⟶a020⟶a220⟶a222⟶b112⟶b210⟶a-1122⟶a-1111⟶a-1110⟶a-1010⟶a-1201⟶a-1021⟶a-1202⟶b-1211⟶a120⟶a221⟶a200⟶a002⟶a022⟶a212⟶b-1121⟶a-1011⟶a-1001⟶a-1100⟶b-1000.



---

*Source: 206930-2011-08-09.xml*