ISSN 2590-9770
The Art of Discrete and Applied Mathematics 3 (2020) #P1.01
https://doi.org/10.26493/2590-9770.1254.266
(Also available at http://adam-journal.eu)
Digraphs with small automorphism groups
that are Cayley on two nonisomorphic groups∗
Luke Morgan †
Centre for the Mathematics of Symmetry and Computation,
Department of Mathematics and Statistics (M019), The University of Western Australia,
35 Stirling Highway, Crawley, 6009, Australia
Current address: University of Primorska, FAMNIT, Glagoljaška 8, 6000 Koper, Slovenia,
and University of Primorska, IAM, Muzejski trg 2, 6000 Koper, Slovenia
Joy Morris ‡
Department of Mathematics and Computer Science, University of Lethbridge,
Lethbridge, AB T1K 3M4, Canada
Gabriel Verret
Department of Mathematics, The University of Auckland,
Private Bag 92019, Auckland 1142, New Zealand
Received 5 November 2018, accepted 30 April 2019, published online 9 January 2020
Abstract
Let Γ = Cay(G,S) be a Cayley digraph on a group G and let A = Aut(Γ). The
Cayley index of Γ is |A : G|. It has previously been shown that, if p is a prime, G is a
cyclic p-group and A contains a noncyclic regular subgroup, then the Cayley index of Γ is
superexponential in p.
We present evidence suggesting that cyclic groups are exceptional in this respect. Specif-
ically, we establish the contrasting result that, if p is an odd prime and G is abelian but not
cyclic, and has order a power of p at least p3, then there is a Cayley digraph Γ on G whose
Cayley index is just p, and whose automorphism group contains a nonabelian regular sub-
group.
∗We thank the referee for their comments on the paper. The first and third authors also thank the second author
and the University of Lethbridge for hospitality.
†The first author was supported by the Australian Research Council grant DE160100081.
‡The second author was supported by the Natural Science and Engineering Research Council of Canada grant
RGPIN-2017-04905.
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
2 Art Discrete Appl. Math. 3 (2020) #P1.01
Keywords: Cayley digraphs, Cayley index.
Math. Subj. Class.: 05C25, 20B25
1 Introduction
Every digraph and group in this paper is finite. A digraph Γ consists of a set of vertices
V(Γ) and a set of arcs A(Γ), each arc being an ordered pair of distinct vertices. (Our
digraphs do not have loops.) We say that Γ is a graph if, for every arc (u, v) of Γ, (v, u) is
also an arc. Otherwise, Γ is a proper digraph.
The automorphisms of Γ are the permutations of V(Γ) that preserve A(Γ). They form
a group under composition, denoted Aut(Γ).
Let G be a group and let S be a subset of G that does not contain the identity. The
Cayley digraph on G with connection set S is Γ = Cay(G,S), the digraph with vertex-set
G and where (u, v) ∈ A(Γ) whenever vu−1 ∈ S. The index of G in Aut(Γ) is called the
Cayley index of Γ.
It is well-known that a digraph is a Cayley digraph onG if and only if its automorphism
group contains the right regular representation of G. A digraph may have more than one
regular subgroup in its automorphism group and hence more than one representation as a
Cayley digraph. This is an interesting situation that has been studied in [2, 9, 12, 13, 15],
for example.
Let p be a prime. Joseph [7] proved that if Γ has order p2 and Aut(Γ) has two regular
subgroups, one of which is cyclic and the other not, then Γ has Cayley index at least pp−1.
The second author generalised this in [11], showing that if p > 3, Γ has order pn and
Aut(Γ) has two regular subgroups, one of which is cyclic and the other not, then Γ has
Cayley index at least pnp−p−n+1. A simpler proof of this was later published in [1]. Kovács
and Servatius [8] proved the analogous result when p = 2.
The theme of the results above is that if Aut(Γ) has two regular subgroups, one of
which is cyclic and the other not, then Γ must have “large” Cayley index. The goal of this
paper is to show that cyclic p-groups are exceptional with respect to this property, at least
among abelian p-groups. More precisely, we prove the following.
Theorem 1.1. Let p be an odd prime and let G be an abelian p-group. If G has order at
least p3 and is not cyclic, then there exists a proper Cayley digraph on G with Cayley index
p and whose automorphism group contains a nonabelian regular subgroup.
It would be interesting to generalise Theorem 1.1 to nonabelian p-groups and to 2-
groups. More generally, we expect that “most” groups admit a Cayley digraph of “small”
Cayley index such that the automorphism group of the digraph contains another (or even a
nonisomorphic) regular subgroup. At the moment, we do not know how to approach this
problem in general, or even what a sensible definition of “small” might be. (Lemma 3.2
shows that the smallest index of a proper subgroup of either of the regular subgroups is a
lower bound – and hence that the Cayley index of p in Theorem 1.1 is best possible.) As
an example, we prove the following.
E-mail addresses: luke.morgan@famnit.upr.si (Luke Morgan), joy.morris@uleth.ca (Joy Morris),
g.verret@auckland.ac.nz (Gabriel Verret)
L. Morgan et al.: Digraphs with small automorphism groups that are Cayley on two . . . 3
Proposition 1.2. Let G be a group generated by an involution x and an element y of order
3, and such that Z6  G  Z3 oZ2. IfG has a subgroupH of index 2, then there is a Cayley
digraph Γ with Cayley index 2 such that Aut(Γ) contains a regular subgroup distinct from
G and isomorphic to H × Z2.
This paper is laid out as follows. Section 2 includes structural results on cartesian prod-
ucts of digraphs that will be required in the proofs of our main results, while in Section 3
we collect results about automorphism groups of digraphs. Section 4 consists of the proof
of Theorem 1.1. Finally, in Section 5 we prove Proposition 1.2 and consider the case of
symmetric groups.
2 Cartesian products
The main result of this section is a version of a result about cartesian products of graphs
due to Imrich [6, Theorem 1] that is adapted to the case of proper digraphs. Imrich’s proof
can be generalised directly to all digraphs, but his proof involves a detailed case-by-case
analysis for small graphs, which can be avoided by restricting attention to proper digraphs.
Generally, there are two notions of connectedness for digraphs: a digraph is weakly
connected if its underlying graph is connected, and strongly connected if for every ordered
pair of vertices there is a directed path from the first to the second. In a finite Cayley
digraph, these notions coincide (see [4, Lemma 2.6.1] for example). For this reason, we
will refer to Cayley digraphs as simply being connected or disconnected.
The complement of a digraph Γ, denoted by Γ, is the digraph with vertex-set V(Γ),
with (u, v) ∈ A(Γ) if and only if (u, v) 6∈ A(Γ), for every two distinct vertices u and v of
Γ. It is easy to see that a digraph and its complement have the same automorphism group.
Given digraphs Γ and ∆, the cartesian product Γ∆ is the digraph with vertex-set
V(Γ) × V(∆) and with ((u, v), (u′, v′)) being an arc if and only if either u = u′ and
(v, v′) ∈ A(∆), or v = v′ and (u, u′) ∈ A(Γ). For each u ∈ V(Γ), we obtain a copy ∆u of
∆ in Γ∆, the induced digraph on {(u, v) | v ∈ V(∆)}. Similarly, for each v ∈ V(∆),
we obtain a copy Γv of Γ in Γ∆ (defined analogously).
A digraph Γ is prime with respect to the cartesian product if the existence of an isomor-
phism from Γ to Γ1Γ2 implies that either Γ1 or Γ2 has order 1, so that Γ is isomorphic
to either Γ1 or Γ2.
It is well known that, with respect to the cartesian product, graphs can be factorised
uniquely as a product of prime factors. Digraphs also have this property.
Theorem 2.1 (Walker, [14]). Let Γ1, . . . ,Γk,Γ′1, . . . ,Γ′` be weakly connected prime di-
graphs. If α is an isomorphism from Γ1 · · ·Γk to Γ′1 · · ·Γ′`, then k = ` and there
exist a permutation π of {1, . . . , k} and isomorphisms αi from Γi to Γ′π(i) such that α is
the product of the αis (1 6 i 6 k).
Theorem 2.1 is a corollary of [14, Theorem 10], as noted in the “Applications” section
of [14], but is more commonly proved by replacing a digraph Γ by its shadow S(Γ) (by
replacing arcs and digons with edges), noting that S(Γ1Γ2) = S(Γ1)S(Γ2), and
using the unique prime factorisation for graphs with respect to the cartesian product.
We now present the version of Imrich’s result that applies to proper digraphs. During
the refereeing process of this article, we were made aware of [5, Theorem 1], which is
similar to the theorem below.
4 Art Discrete Appl. Math. 3 (2020) #P1.01
Theorem 2.2. If Γ is a proper digraph, then at least one of Γ or Γ is prime with respect
to cartesian product and is weakly connected.
Proof. We first make a key observation. Let u = (x, y) and v = (x′, y) be distinct vertices
of a cartesian product X Y lying in the same copy Xy of X . If w = (z, y′) is a vertex
adjacent to both u and v (with no specification on the direction of the arcs), we claim that
w ∈ Xy . Indeed, since w ∼ u, if y 6= y′, then z = x and y ∼ y′ in Y . It follows that
w = (x, y′) cannot be adjacent to v = (x′, y) in X Y since x 6= x′. Hence y = y′ and
w ∈ Xy .
Suppose that either Γ or Γ is not weakly connected, say Γ. Then Γ is weakly connected.
We may assume that Γ admits a non-trivial factorisation as Γ = X Y (so that X and Y
have at least two vertices).
Suppose there exist a weakly connected component C of Γ and a copy of X , Xy say,
such that Xy has two vertices that are not in C, u and v say. By the key observation applied
to Γ, every vertex of C is also in Xy . Let c ∈ C and let y′ ∈ Y with y′ 6= y. Then, since
C is contained in Xy , there are at least two vertices of Xy′ with no arc in Γ in common
with c. Applying the key observation yields that c is in Xy
′
, which is a contradiction. We
may thus assume that every weakly connected component of Γ misses at most one vertex
from each copy of X . In particular, Γ has exactly two weakly connected components, and
therefore X has exactly two vertices. A symmetric argument yields that Y also has two
vertices and thus Γ has four vertices, and the result can be checked by brute force.
Now we may assume that both Γ and Γ are weakly connected. Towards a contradiction,
assume that Γ = AB and that ϕ is an isomorphism from Γ to C D, where A, B, C,
and D all have at least 2 vertices.
Since Γ is a proper digraph, without loss of generality so is A, and A has an arc (a, a′)
such that (a′, a) is not an arc of A. Let b be a vertex of B.
Pick b′ to be a vertex ofB distinct from b. We claim thatϕ((a, b)), ϕ((a′, b)), ϕ((a, b′)),
ϕ((a′, b′)) all lie in some copy of either C or D. The digraph in Figure 1 is the subdigraph
of Γ under consideration.
(a; b) (a0; b)
(a; b0) (a0; b0)
Figure 1: A subdigraph of Γ.
Since every arc in C D lies in either a copy of C or D, we may assume that the
arc from ϕ((a, b)) to ϕ((a′, b′)) lies in some copy Cd of C, say ϕ((a, b)) = (c, d) and
ϕ((a′, b′)) = (c′, d), with c, c′ ∈ V(C) and d ∈ V(D). Towards a contradiction, suppose
that ϕ((a′, b)) /∈ Cd. Then the arc from ϕ((a′, b)) to (c, d) must lie in Dc, so ϕ((a′, b)) =
(c, d′) for some vertex d′ of D. Since there is a path of length 2 via ϕ((a, b′)) from (c′, d)
L. Morgan et al.: Digraphs with small automorphism groups that are Cayley on two . . . 5
to (c, d′) and since ϕ((a, b′)) 6= (c, d) = ϕ((a, b)), we must have ϕ((a, b′)) = (c′, d′). But
now we have an arc from (c, d′) to (c, d) and an arc from (c′, d) to (c′, d′), so arcs in both
directions between d and d′ inD. This implies that there are arcs in both directions between
(c, d) = ϕ((a, b)) and (c, d′) = ϕ((a′, b)), a contradiction. Hence ϕ((a′, b)) ∈ Cd, and by
the observation in the first paragraph, we have ϕ((a, b′)) ∈ Cd also. This proves the claim.
By repeatedly applying the claim, all elements of ϕ({a, a′} × V(B)) lie in some copy
of C or D, say, Cd. Let a′′ ∈ V(A) − {a, a′} and let b and b′ be distinct vertices of B.
By the definitions of cartesian product and complement, there are arcs in both directions
between (a′′, b) and (a, b′) and between (a′′, b) and (a′, b′). Thus, by the observation in the
first paragraph, ϕ((a′′, b)) also lies in Cd. This shows that every vertex of Γ lies in Cd, so
D is trivial. This is the desired contradiction.
Remark 2.3. Imrich’s Theorem [6, Theorem 1] states that, for every graph Γ, either Γ or
Γ is prime with respect to the cartesian product, with the following exceptions: K2K2,
K2K2, K2K2K2, K4K2, K2K−4 , and K3K3, where Kn denotes the com-
plete graph on n vertices and K−4 denotes K4 with an edge deleted. These would therefore
be the complete list of exceptions to Theorem 2.2 if we removed the word ‘proper’ from
the hypothesis.
Remark 2.4. While most of our results apply only to finite digraphs, Theorem 2.2 also
applies to infinite ones (as does Imrich’s Theorem). The proof is the same.
Corollary 2.5. Let Γ1 be a proper Cayley digraph on G with Cayley index i1 and let
Γ2 be a connected Cayley digraph on H with Cayley index i2. If i1 > i2, then at least
one of Γ1Γ2 or Γ1Γ2 has automorphism group equal to Aut(Γ1)× Aut(Γ2) and, in
particular, is a proper Cayley digraph on G×H with Cayley index i1i2.
Proof. By Theorem 2.2, one of Γ1 and Γ1 is connected and prime with respect to the carte-
sian product, say Γ1 without loss of generality. Clearly, we have Aut(Γ1) × Aut(Γ2) 6
Aut(Γ1Γ2). Since i1 > i2, Γ1 cannot be a cartesian factor of Γ2. It follows by Theo-
rem 2.1 that every automorphism of Γ1Γ2 is a product of an automorphism of Γ1 and an
automorphism of Γ2, so that Aut(Γ1)×Aut(Γ2) = Aut(Γ1Γ2).
3 Additional background
The following lemma is well known and easy to prove.
Lemma 3.1. Let G be a group, let S ⊆ G and let α ∈ Aut(G). If Sα = S, then α induces
an automorphism of Cay(G,S) which fixes the vertex corresponding to the identity.
The next lemma is not used in any of our proofs, but it shows that the Cayley indices in
Theorem 1.1 and Theorem 1.2 are as small as possible.
Lemma 3.2. If Cay(G,S) has Cayley index i and Aut(Cay(G,S)) has at least two reg-
ular subgroups, then G has a proper subgroup of index at most i.
Proof. Let A = Aut(Cay(G,S)) and let H be a regular subgroup of A different from
G. Clearly, G ∩ H is a proper subgroup of G and we have |A| > |GH| = |G||H||G∩H| hence
i = |A : G| = |A : H| > |G : G ∩H|.
6 Art Discrete Appl. Math. 3 (2020) #P1.01
If v is vertex of a digraph Γ, then Γ+(v) denotes the out-neighbourhood of v, that is,
the set of vertices w of Γ such that (v, w) is an arc of Γ.
Let A be a group of automorphisms of a digraph Γ. For v ∈ V(Γ) and i > 1, we use
A
+[i]
v to denote the subgroup of Av that fixes every vertex u for which there is a directed
path of length at most i from v to u.
Lemma 3.3. Let Γ be a connected digraph, let v be a vertex of Γ and let A be a transitive
group of automorphisms of Γ. If A+[1]v = A
+[2]
v , then A
+[1]
v = 1.
Proof. By the transitivity ofA, we haveA+[1]u = A
+[2]
u for every vertex u. Using induction
on i, it easily follows that, for every i > 1, we have A+[i]v = A
+[i+1]
v . By connectedness,
this implies that A+[1]v = 1.
Lemma 3.4. Let p be a prime and let A be a permutation group whose order is a power
of p. If A has a regular abelian subgroup G of index p and G has a subgroup M of index
p that is normalised but not centralised by a point-stabiliser in A, then A has a regular
nonabelian subgroup.
Proof. Let Av be a point-stabiliser in A. Note that A = Go Av and that |Av| = p. Since
M is normal in G and normalised by Av , it is normal in A and has index p2. Clearly,
M o Av 6= G hence A/M contains at least two subgroups of order p and must therefore
be elementary abelian.
Let α be a generator of Av and let g ∈ G −M . By the previous paragraph, we have
(gα)p ∈ M . Let H = 〈M, gα〉. Since M is centralised by g but not by α, it is not
centralised by gα hence H is nonabelian. Further, we have |H| = p|M | = |G|, so that H
is normal in A. If H was non-regular, it would contain all point-stabilisers of A, and thus
would contain α and hence also g. This would give G = 〈M, g〉 6 H , a contradiction.
Thus H is a regular nonabelian subgroup of A.
4 Proof of Theorem 1.1
Throughout this section, p denotes an odd prime. In Section 4.1, we show that Theorem 1.1
holds when G ∼= Z3p. In Sections 4.2 and 4.3, we subdivide abelian groups of rank 2 and
order at least p3 into two families, and show that the theorem holds for all such groups.
Finally, in Section 4.4, we explain how these results can be applied to show that the theorem
holds for all abelian groups of order at least p3.
4.1 G ∼= Z3p
Write G = 〈x, y, z〉, let α be the automorphism of G that maps (x, y, z) to (xy, yz, z), let
S = {xαi , yαi : i ∈ Z}, let Γ = Cay(G,S), and let A = Aut(Γ). Note that Γ is a proper
digraph (this will be needed in Section 4.4).
It is easy to see that, for i ∈ N, we have xαi = xyiz(
i
2), yα
i
= yzi and zα
i
= z. In
particular, α has order p and |S| = 2p. By Lemma 3.1, G o 〈α〉 6 A. We will show that
equality holds.
Using the formulas above, it is not hard to see that the induced digraph on S has exactly
2p arcs: (xα
i
, xα
i+1
) and (yα
i
, xα
i+1
), where i ∈ Zp. Thus, for every s ∈ S,A1,s = A+[1]1 .
By vertex-transitivity, Au,v = A
+[1]
u for every arc (u, v).
L. Morgan et al.: Digraphs with small automorphism groups that are Cayley on two . . . 7
Let s ∈ S. We have already seen that A1,s = A+[1]1 . Let t ∈ S. From the structure of
the induced digraph on S = Γ+(1), we see that t has an out-neighbour in S, so that both
t and this out-neighbour are fixed by A1,s. It follows that A1,s fixes all out-neighbours of
t. We have shown that A1,s = A
+[2]
1 . By Lemma 3.3, it follows that A1,s = 1. Since the
induced digraph on S is not vertex-transitive and α ∈ A1, the A1-orbits on S have length
p. Hence |A1| = p|A1,s| = p. Thus, Γ has Cayley index p and A = G o 〈α〉. Finally,
we apply Lemma 3.4 with M = 〈y, z〉 to deduce that A contains a nonabelian regular
subgroup.
4.2 G ∼= Zpn × Zp with n > 2
Choose x, y ∈ G of order pn and p respectively so that G = 〈x, y〉. Let x0 = xp
n−1
, let α
be the automorphism of G that maps (x, y) to (xy, x0y), let S = {xα
i
, yα
i
: i ∈ Z} and
let Γ = Cay(G,S). Again, note that Γ is a proper digraph.
Since n > 2, x0 is fixed by α. It follows that, for i ∈ N, we have xα
i
= xyix
(i2)
0 and
yα
i
= yxi0. In particular, α has order p and |S| = 2p.
Using these formulas, it is not hard to see that the induced digraph on S has exactly
2p arcs: (xα
i
, xα
i+1
) and (yα
i
, xα
i+1
), where i ∈ Zp. The proof is now exactly as in the
previous section, except that we use M = 〈xp, y〉 when applying Lemma 3.4.
4.3 G ∼= Zpn × Zpm with n > m > 2
Choose x, y ∈ G of order pn and pm respectively so that G = 〈x, y〉. Let x0 = xp
n−1
,
let y0 = yp
m−1
, let α be the automorphism of G that maps (x, y) to (xy0, yx0), let S =
{xαi , yαi , (xy−1)αi : i ∈ Z}, let Γ = Cay(G,S), and let A = Aut(Γ). Again, note that
Γ is a proper digraph.
Since n > m > 2, x0 and y0 are both fixed by α. It follows that, for i ∈ N, we have
xα
i
= xyi0, and y
αi = yxi0. In particular, α has order p and |S| = 3p. By Lemma 3.1,
Go 〈α〉 6 A.
Using the formulas above, it is not hard to see that the induced digraph on S has exactly
2p arcs: ((xy−1)α
i
, xα
i
) and (yα
i
, xα
i
), where i ∈ Zp. It follows that |A1 : A1,x| = p.
We will show that A1,x = 1, which will imply that A = Go 〈α〉.
Let X = {xαi : i ∈ Z} = x〈y0〉, Y = {xα
i
: i ∈ Z} = y〈x0〉 and Z = {(xy−1)α
i
:
i ∈ Z} = xy−1〈x−10 y0〉. It follows from the previous paragraph that X is an orbit of A1
on S.
Note that the p elements of Y 2 = y2〈x0〉 are out-neighbours of every element of Y .
Similarly, the p elements of Z2 are out-neighbours of every element of Z. On the other
hand, one can check that an element of Y and an element of Z have a unique out-neighbour
in common, namely their product. This shows that Y and Z are blocks for A1. We claim
that Y and Z are orbits of A1.
Let Y1 = Y and, for i > 2, inductively define Yi =
⋂
x∈Yi−1 Γ
+(x). Define Zi
analogously. Let g ∈ A1. By induction, Y gi ∈ {Yi, Zi}, and Y
g
i = Zi if and only if
Y g = Z. Note that Yi = Y i = yi〈x0〉 and Zi = Zi = xiy−i〈x−10 y0〉. If n = m, then
1 ∈ x0y−10 〈x
−1
0 y0〉 = Zpm−1 , but 1 /∈ y0〈x0〉 = Ypm−1 , so Y and Z are orbits for A1. We
may thus assume that n > m. Note that y0 ∈ y0〈x0〉 = Ypm−1 , and y0 is an in-neighbour
of x ∈ X . However, Zpm−1 = xp
m−1
y−10 〈x
−1
0 y0〉. Since n > m, we see that no vertex of
8 Art Discrete Appl. Math. 3 (2020) #P1.01
Zpm−1 is an in-neighbour of a vertex ofX . Again it follows that Y and Z are orbits for A1.
Considering the structure of the induced digraph on S, it follows that, for every s ∈ S,
A1,s = A
+[1]
1 . By vertex-transitivity, Au,v = A
+[1]
u for every arc (u, v). Since elements of
Y and Z have an out-neighbour in S, A1,x fixes the out-neighbours of elements of Y and
Z. Furthermore, for every i ∈ Z, xyi0y is a common out-neighbour of xyi0 and y, hence it
is fixed by A1,x. Thus, every element of X has an out-neighbour fixed by A1,x. It follows
that A1,x fixes all out-neighbours of elements of X and thus A1,x = A
+[1]
1 = A
+[2]
1 . By
Lemma 3.3, it follows that A1,x = 1. As in Section 4.1, we can also conclude |A1| = p,
Γ has Cayley index p and A = G o 〈α〉. Finally, applying Lemma 3.4 with M = 〈xp, y〉
implies that A contains a nonabelian regular subgroup.
4.4 General case
Recall that G is an abelian p-group that has order at least p3 and is not cyclic. By the
Fundamental Theorem of Finite Abelian Groups, we can write G = G1 × G2, where G1
falls into one of the three cases that have already been dealt with in this section.
(More explicitly, if G is not elementary abelian, then we can take G1 isomorphic to
Zpn × Zpm with n > 2 and m > 1. If G is elementary abelian, then, since |G| > p3, we
can take G1 isomorphic to Z3p.)
We showed in the previous three sections that there exists a proper Cayley digraph Γ1
on G1 with Cayley index equal to p and whose automorphism group contains a nonabelian
regular subgroup.
Note that every cyclic group admits a prime, connected Cayley digraph whose Cayley
index is 1. (For example, the directed cycle of the corresponding order.) Since G2 is a
direct product of cyclic groups, applying Corollary 2.5 iteratively yields a proper connected
Cayley digraph Γ on G1 × G2 with automorphism group Aut(Γ1) × G2. In particular, Γ
has Cayley index p and its automorphism group contains a nonabelian regular subgroup.
This concludes the proof of Theorem 1.1.
In fact, the proof above yields the following stronger result.
Theorem 4.1. Let G be an abelian group. If there is an odd prime p such that the Sylow p-
subgroup of G is neither cyclic nor elementary abelian of rank 2, then G admits a proper
Cayley digraph with Cayley index p whose automorphism group contains a nonabelian
regular subgroup.
5 Proof of Proposition 1.2
We begin with a lemma that helps to establish the existence of regular subgroups.
Lemma 5.1. Let G be a group with nontrivial subgroups H and B such that G = HB
and H ∩ B = 1, and let Γ = Cay(G,S) be a Cayley digraph on G. If S is closed under
conjugation by B, then Aut(Γ) has a regular subgroup distinct from the right regular
representation of G and isomorphic to H ×B.
Proof. Let A = Aut(Γ). For g ∈ G, let `g and rg denote the permutations of G induced
by left and right multiplication by g, respectively. Similarly, for g ∈ G, let cg denote the
permutation of G induced by conjugation by g. For X 6 G, let RX = 〈rx : x ∈ X〉.
Let LB = 〈`b : b ∈ B〉 and CB = 〈cb : b ∈ B〉. Note that RH 6 A. For every g ∈ G,
L. Morgan et al.: Digraphs with small automorphism groups that are Cayley on two . . . 9
rgcg−1 = `g . For all b ∈ B, we have rb ∈ A and, since S is closed under conjugation by
B, cb−1 ∈ A hence LB 6 A.
Let K = 〈LB , RH〉. If K = RG, then LB 6 RG which implies that CB 6 RG,
contradicting the fact that RG is regular. Thus K 6= RG. Note that LB and RH commute.
Suppose that k ∈ RH ∩ LB , so k = rh = `b for some h ∈ H and some b ∈ B. Thus
h = 1rh = 1k = 1`b = b.
Since H ∩ B = 1, this implies k = 1. It follows that RH ∩ LB = 1 and hence
K = RH × LB ∼= H × B. Finally, suppose that some k = rh`b ∈ K fixes 1. It follows
that 1rh`b = 1 = bh so that b ∈ H , a contradiction. This implies that K is regular, which
concludes the proof.
We now prove a general result, which together with Lemma 5.1 will imply Proposi-
tion 1.2.
Proposition 5.2. Let G be a group generated by an involution x and an element y of
order 3, let S = {x, y, yx} and let Γ = Cay(G,S). If G is isomorphic to neither Z6 nor
Z3 o Z2 ∼= Z23 o Z2, then Γ has Cayley index 2.
Proof. Clearly, Γ is connected. Since G is not isomorphic to Z6, we have yx 6= y. In
particular, we have |S| = 3. If yx = y−1, then G ∼= Sym(3) and the result can be checked
directly. We therefore assume that yx 6= y−1. Since G  Z3 o Z2, we have yxy 6= yyx.
We have that Γ+(x) = {1, yx, xy}, Γ+(y) = {xy, y2, yxy} and Γ+(yx) = {yx, yyx,
(y2)x}. One can check that the only equalities between elements of these sets are the ones
between elements having the same representation. In other words,
|{1, yx, xy, y2, yxy, yyx, (y2)x}| = 7.
(For example, if yx = yxy, then xy
−1
= yx, contradicting the fact that x and y have
different orders.)
Let A = Aut(Γ) and let cx denote conjugation by x. Note that cx ∈ A1. We first show
that A+[1]1 = 1. It can be checked that y
2 is the unique out-neighbour of y that is also an
in-neighbour of 1, hence it is fixed by A+[1]1 , and so is (y
2)x by analogous reasoning. We
have seen earlier that xy is the unique common out-neighbour of x and y, hence it too is
fixed by A+[1]1 , and similarly for yx. Being the only remaining out-neighbours of y, y
xy
must be also fixed, and similarly for yyx. Thus A+[1]1 = A
+[2]
1 . Since Γ is connected,
Lemma 3.3 implies that A+[1]1 = 1.
Note that x is the only out-neighbour of 1 that is also an in-neighbour, hence it is fixed
by A1, whereas cx interchanges y and yx. It follows that |A1| = |A1 : A+[1]1 | = 2 and Γ
has Cayley index 2, as desired.
Proof of Proposition 1.2. Let Γ = Cay(G, {x, y, yx}). By Proposition 5.2, Γ has Cayley
index 2. Since |G : H| = 2 and y has order 3, we have y ∈ H . As 〈x, y〉 = G, we
have x /∈ H and G = H o 〈x〉. Clearly, {x, y, yx} is closed under conjugation by x. It
follows by Lemma 5.1 that Aut(Γ) has a regular subgroup distinct from G and isomorphic
to H × 〈x〉 ∼= H × Z2.
10 Art Discrete Appl. Math. 3 (2020) #P1.01
It was shown by Miller [10] that, when n > 9, Sym(n) admits a generating set con-
sisting of an element of order 2 and one of order 3; this is also true when n ∈ {3, 4}. In
these cases, we can apply Proposition 1.2 with H = Alt(n) to obtain a Cayley digraph
on Sym(n) that has Cayley index 2 and whose automorphism group contains a regular
subgroup isomorphic to Alt(n)× Z2.
A short alternate proof of this fact can be derived from a result of Feng [3]. This yields
a Cayley graph and is valid for n > 5.
Proposition 5.3. If n > 5, then there is a Cayley graph on Sym(n) with Cayley index 2,
whose automorphism group contains a regular subgroup isomorphic to Alt(n)× Z2.
Proof. Let T = {(1 2), (2 3), (2 4)} ∪ {(i i + 1) : 4 6 i 6 n − 1} and let Γ =
Cay(Sym(n), T ). Note that all elements of T are transpositions. Let Tra(T ) be the trans-
position graph of T , that is, the graph with vertex-set {1, . . . , n} and with an edge {i, j}
if and only if (i j) ∈ T . Note that Tra(T ) is a tree and thus T is a minimal generating
set for Sym(n) (see for example [4, Section 3.10]). Let B = 〈(1 3)〉. Since n > 5,
Aut(Tra(T )) = B. It follows by [3, Theorem 2.1] that Aut(Γ) ∼= Sym(n) o B. In
particular, Γ has Cayley index 2.
Note that Sym(n) = Alt(n)oB and that T is closed under conjugation byB. Applying
Lemma 5.1 with H = Alt(n) shows that Aut(Γ) has a regular subgroup isomorphic to
Alt(n)× Z2.
ORCID iDs
Luke Morgan https://orcid.org/0000-0003-2396-5430
Gabriel Verret https://orcid.org/0000-0003-1766-4834
References
[1] B. Alspach and S. Du, Suborbit structure of permutation p-groups and an application to Cayley
digraph isomorphism, Canad. Math. Bull. 47 (2004), 161–167, doi:10.4153/cmb-2004-017-9.
[2] J. Bamberg and M. Giudici, Point regular groups of automorphisms of generalised quadrangles,
J. Comb. Theory Ser. A 118 (2011), 1114–1128, doi:10.1016/j.jcta.2010.11.004.
[3] Y.-Q. Feng, Automorphism groups of Cayley graphs on symmetric groups with generating
transposition sets, J. Comb. Theory Ser. B 96 (2006), 67–72, doi:10.1016/j.jctb.2005.06.010.
[4] C. Godsil and G. Royle, Algebraic Graph Theory, volume 207 of Graduate Texts in Mathemat-
ics, Springer-Verlag, New York, 2001, doi:10.1007/978-1-4613-0163-9.
[5] M. Grech, W. Imrich, A. D. Krystek and Ł. J. Wojakowski, Direct product of automorphism
groups of digraphs, Ars Math. Contemp. 17 (2019), 89–101, doi:10.26493/1855-3974.1498.
77b.
[6] W. Imrich, On products of graphs and regular groups, Israel J. Math. 11 (1972), 258–264,
doi:10.1007/bf02789317.
[7] A. Joseph, The isomorphism problem for Cayley digraphs on groups of prime-squared order,
Discrete Math. 141 (1995), 173–183, doi:10.1016/0012-365x(93)e0215-p.
[8] I. Kovács and M. Servatius, On Cayley digraphs on nonisomorphic 2-groups, J. Graph Theory
70 (2012), 435–448, doi:10.1002/jgt.20625.
[9] D. Marušič and J. Morris, Normal circulant graphs with noncyclic regular subgroups, J. Graph
Theory 50 (2005), 13–24, doi:10.1002/jgt.20088.
L. Morgan et al.: Digraphs with small automorphism groups that are Cayley on two . . . 11
[10] G. A. Miller, On the groups generated by two operators, Bull. Amer. Math. Soc. 7 (1901),
424–426, doi:10.1090/s0002-9904-1901-00826-9.
[11] J. Morris, Isomorphic Cayley graphs on nonisomorphic groups, J. Graph Theory 31 (1999),
345–362, doi:10.1002/(sici)1097-0118(199908)31:4〈345::aid-jgt9〉3.3.co;2-m.
[12] G. F. Royle, A normal non-Cayley-invariant graph for the elementary abelian group of order
64, J. Aust. Math. Soc. 85 (2008), 347–351, doi:10.1017/s1446788708000931.
[13] P. Spiga, Enumerating groups acting regularly on a d-dimensional cube, Comm. Algebra 37
(2009), 2540–2545, doi:10.1080/00927870902766308.
[14] J. W. Walker, Strict refinement for graphs and digraphs, J. Comb. Theory Ser. B 43 (1987),
140–150, doi:10.1016/0095-8956(87)90018-9.
[15] B. Zgrablić, On quasiabelian Cayley graphs and graphical doubly regular representations, in:
S. Klavžar, D. Marušič and B. Mohar (eds.), Algebraic and Topological Methods in Graph
Theory, Elsevier, Amsterdam, pp. 495–519, 2002, doi:10.1016/s0012-365x(01)00104-2, pa-
pers from the 4th Slovenian Graph Theory Conference held at Lake Bled, June 28 – July 2,
1999.