Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 3 (2010) 201–214
Asymptotic automorphism groups of
Cayley digraphs and graphs of abelian groups of
prime-power order
Edward Dobson
Department of Mathematics and Statistics, Mississippi State University
PO Drawer MA Mississippi State, MS 39762
Received 6 October 2009, accepted 21 October 2010, published online 17 November 2010
Abstract
We show that almost every Cayley graph Γ of an abelian group G of odd prime-power
order has automorphism group as small as possible. Additionally, we show that almost
every Cayley (di)graph Γ of an abelian group G of odd prime-power order that does not
have automorphism group as small as possible is a normal Cayley (di)graph of G (that is,
GL/Aut(Γ)).
Keywords: Cayley graph, abelian group, automorphism group, asymptotic, p-group
Math. Subj. Class.: 05C25
Determining the full automorphism group of a Cayley graph or digraph is one of the
most fundamental questions that one can ask about a Cayley graph. While it is usually
quite difficult to determine the automorphism group of a Cayley graph or digraph, some-
what surprisingly for some rather general groups G it has been shown that almost every
Cayley graph and digraph of the groups in these classes has automorphism group as small
as possible. That is, if Γ is a Cayley (di)graph of G, then with probability approaching 1
as |G| → ∞, the automorphism group of Γ is GL. Indeed, while working on the prob-
lem (now solved, see [15] for graphs and [3, 4] for digraphs) of determining which groups
G have a digraphical regular representation (a Cayley digraph Γ of G with automorphism
group Aut(Γ) = G), or DRR, and which groups G have a graphical regular representation
(a Cayley graph Γ of G with Aut(Γ) = G), or GRR, Babai, Godsil, Imrich, and Lovász
(see [5]) conjectured that unless G is an abelian or a generalized dicyclic group, almost
all Cayley digraphs of G are GRR’s, while for digraphs, the conjecture is that almost all
Cayley graphs of G are DRR’s. (For graphs, it is known that no Cayley graphs of groups
that are not elementary abelian 2-groups nor dicyclic are GRR’s.)
E-mail address: dobson@math.msstate.edu (Edward Dobson)
Copyright c© 2010 DMFA Slovenije
202 Ars Math. Contemp. 3 (2010) 201–214
In terms of verifying these conjectures, in 1981 Godsil [16] showed that almost all
Cayley digraphs of groups G of prime-power order are DRR’s provided that there is no
homomorphism from G onto Zp o Zp. Additionally, Babai and Godsil [5] proved that
almost every Cayley digraph of a nilpotent group G is a DRR. Godsil [16] showed that for
every other group G (i.e. G is not abelian nor generalized dicyclic) of prime-power order
with no homomorphism onto Zp o Zp, almost all Cayley graphs of G are GRR’s, while
Babai and Godsil [5] showed that for every nilpotent but not abelian group G, almost every
Cayley graph of G is a GRR. Babai and Godsil also considered whether or not almost all
Cayley graphs of an abelian groupG has automorphism group as small as possible (namely
of order 2|G|), and showed that this was indeed the case for almost all such Cayley graphs
provided that the order of G is congruent to 3 modulo 4.
In this paper, we will consider the asymptotic automorphism groups of Cayley graphs
and digraphs of abelian groups of odd prime-power order. First, as it will not involve
much additional work, we will prove in Theorem 1.7 the known result that almost all Cay-
ley digraphs of an abelian group G of odd prime-power order have automorphism group
GL. In Theorem 3.3 we show that almost all Cayley graphs of an abelian group G of odd
prime-power order have automorphism groups as small as possible, namely of order 2|G|,
removing the restriction that |G| ≡ 3 (mod 4) for these groups. M.-Y. Xu [27] introduced
the notion of a normal Cayley (di)graph of a group G, that is, a Cayley (di)graph Γ of a
group G such that GL/Aut(Γ), and he conjectured that almost all Cayley (di)graphs of a
group G are normal Cayley digraphs of G. Of course, if almost all Cayley (di)graphs of
G are GRR’s or DRR’s, then almost all Cayley (di)graphs of a group G are normal Cayley
digraphs of G, so Xu’s conjecture is weaker than the conjectures in the previous paragraph.
We conjecture (Conjecture 4.1) that almost every Cayley (di)graph of G whose automor-
phism group is not as small as possible is a normal Cayley (di)graph of G, and verify
this conjecture for graphs (Theorem 3.5) and digraphs (Theorem 2.9) of abelian groups of
odd prime-power order. We finish with a few additional problems that can be considered
to try to understand more fully the asymptotic behavior automorphism groups of Cayley
(di)graphs.
One final comment is in order about what we mean by “almost all” Cayley digraphs. In
this paper, we first fix a specific abelian group of odd prime-power order. In order then for
the number of group elements to go to infinity without changing the structure of the group,
we must let p approach infinity.
1 DRR’s
In this section, we develop some elementary tools that will be needed for the main results.
Additionally, as it will not take much extra work, we prove that almost every Cayley digraph
of an abelian group of prime-power order is a DRR - a special case of a result of Godsil as
mentioned above - for completeness.
Definition 1.1. Let G be a group and S ⊂ G. We define the Cayley digraph of G with
connection set S to be the digraph Γ = Γ(G,S) defined by V (Γ) = G and E(Γ) =
{(g, gs) : s ∈ S, g ∈ G}. If S = S−1, then Γ is a Cayley graph of G with connection set
S. Note that GL = {x→ gx : g ∈ G} ≤ Aut(Γ).
Lemma 1.2. Let G be a group of finite order n and α ∈ Aut(G), α 6= 1. Then α has at
most 3n/4 orbits in its natural action on G.
E. Dobson: Asymptotic automorphism groups of Cayley digraphs. . . 203
Proof. It is easy to see that the set of all fixed points of α forms a subgroup H of G. Then
|H| ≤ n/2. As each orbit contained in G−H has order at least 2, we see that the number
of orbits of α is at most
|H|+ |G−H|/2 = |H|/2 + |G|/2 ≤ 3n/4.
Similarly, we also have the following result.
Lemma 1.3. Let G be a group of order pk, p a prime, and α ∈ Aut(G) such that |α| has
order a power of p. Then α has at most 2pk−1 − pk−2 orbits.
Proof. As in the previous result, the set of all fixed points of α forms a subgroup H of G,
and so |H| ≤ pk−1. Also, as α has order a power of p, each orbit contained in G−H has
order at least p. We see that the number of orbits of α is at most
|H|+ |G−H|
p
≤ pk−1 + p
k − pk−1
p
= 2pk−1 − pk−2.
We shall have need of the following result.
Lemma 1.4. Let G be a group of prime-power order pk. Then |Aut(G)| ≤ |Aut(Zkp)|.
Proof. LetM be a minimal set of generators of G, with j = |M |. By [18, Chapter III, Satz
3.19],
|Aut(G)| ≤ pj(k−j)Πj−1i=0 (p
j −pi) = Πj−1i=0 (p
k−pipk−j) ≤ Πj−1i=0 (p
k−pi) = |Aut(Zkp)|.
Lemma 1.5. Let k be fixed a positive integer. Then there exists an integer N such that if
pk ≥ N , then |Aut(Zkp)| ≤ 2p
k/8.
Proof. Clearly there exists a positive integer N such that if x ≥ N , then xk ≤ 2x/8.
Letting p be the smallest prime number such that pk ≥ x ≥ N , we see that pk2 ≤ 2pk/8.
Then
|Aut(Zkp)| = Πk−1i=0 (p
k − pi) ≤ pk
2
≤ 2p
k/8.
Definition 1.6. For a group G, we define CayDi(G) to be the set of all Cayley digraphs
of G, and DRR(G) to be the set of all Cayley digraphs of G which are digraphical regular
representations of G. Similarly, we let Cay(G) be the set of all Cayley graphs of G, and
GRR(G) to be the set of all Cayley graphs ofGwhich are graphical regular representations
of G.
204 Ars Math. Contemp. 3 (2010) 201–214
Theorem 1.7. Almost every digraph of an abelian group G of prime-power order pk is a
DRR. More specifically,
lim
p→∞
|DRR(G)|
|CayDi(G)|
= 1.
Proof. LetG be an abelian group of order pk and Γ a Cayley digraph ofG. IfNAut(Γ)(GL) =
GL, then a Sylow p-subgroup of Aut(Γ) must have order pk, and so GL is contained in the
center of its normalizer. By Burnside’s Transfer Theorem [17, Theorem 7.4.3], Aut(Γ) has
a normal p-complement H . As H/Aut(Γ), the orbits of H form a complete block system
B of Aut(Γ), and as the size of an orbit of H divides |H|, we have that blocks of B consist
of blocks of size relatively prime to p. As Γ has order pk, we see that B consists of pk
blocks of size 1. Thus H = 1 and Aut(Γ) = GL. That is, if NAut(Γ)(GL) = GL, then Γ
is a DRR of G.
We now provide an upper bound on the number of Cayley digraphs of G that are not
DRR’s of G, provided that pk ≥ N , where N is as given by Lemma 1.5. Let Γ be
such a digraph. By the argument in the preceding paragraph, NAut(Γ)(GL) 6= GL. As
NSG(GL) = Aut(G) · GL [8, Corollary 4.2B], we see that Aut(Γ) contains a nontrivial
group automorphism α of G. By Lemma 1.2, α has at most 3pk/4 orbits, and as the con-
nection set of Γ must consist of unions of orbits of α, we see that there are at most 23p
k/4
Cayley digraphs of G whose automorphism group contains α. By Lemma 1.4, there are
at most |Aut(Zkp)| possible choices of α, and by Lemma 1.5, |Aut(Zkp)| ≤ 2p
k/8. We
conclude that there are at most 23p
k/4 · 2pk/8 = 27pk/8 Cayley digraphs of G that are not
DRR’s of G. As there are 2p
k
distinct Cayley digraphs of G, we see that
lim
p→∞
|DRR(G)|
|CayDi(G)|
≥ lim
p→∞
2p
k − 27pk/8
2pk
= 1.
2 Normal Cayley Digraphs
In this section we consider the question of whether or not almost all Cayley digraphs of an
abelian group of prime-power order are normal Cayley digraphs.
Definition 2.1. Let Γ be a Cayley digraph of G. We say that Γ is a normal Cayley digraph
of G if GL/Aut(Γ). For a group G, we denote the set of all normal Cayley digraphs
of G by NorCayDi(G). The set of all normal Cayley graphs of G will be denoted by
NorCay(G).
Definition 2.2. LetG be an abelian group of prime-power order pk, so thatG ∼= Πri=1Zpai ,
where
∑r
i=1 ai = k. We define the number of elementary divisors of G to be r, and say G
is of rank r.
Definition 2.3. For H ≤ G, we define the normal closure of H in G, denoted by HG, to
be 〈g−1hg : g ∈ G, h ∈ H〉.
Note that HG/G, and is the smallest normal subgroup of G that contains H .
The following result is [10, Theorem 6.3], and from it, we will obtain the main tool
(Lemma 2.6) used for the rest of the work in this paper.
E. Dobson: Asymptotic automorphism groups of Cayley digraphs. . . 205
Theorem 2.4. Let G ≤ Spk be transitive with an abelian Sylow p-subgroup P of rank t.
If p > 2t−1, then PG is permutation isomorphic to a direct product of cyclic groups and
doubly-transitive nonabelian simple groups with the canonical action, with the number of
factors in the direct product equal to t.
Definition 2.5. Let Ω be a set and G ≤ SΩ. Let G act on Ω × Ω by g(ω1, ω2) =
(g(ω1), g(ω2)) for every g ∈ G and ω1, ω2 ∈ Ω. We define the 2-closure of G, denoted
G(2), to be the largest subgroup of SΩ whose orbits on Ω × Ω are the same as G’s. Let
O1, . . . ,Or be the orbits of G acting on Ω×Ω. Define digraphs Γ1, . . . ,Γr by V (Γi) = Ω
and E(Γi) = Oi. Each Γi, 1 ≤ i ≤ r, is an orbital digraph of G, and it is straightforward
to show that G(2) = ∩ri=1Aut(Γi). Clearly the automorphism group of a graph or digraph
is 2-closed.
Lemma 2.6. Let k be a positive integer, and p a prime such that p > 2k−1. LetG ≤ Spk be
transitive and 2-closed with Sylow p-subgroup P that is abelian. Then one of the following
is true:
1. G has a normal Sylow p-subgroup, or
2. G contains a normal subgroup that is permutation isomorphic to Sp × A, where
A ≤ Spk−1 has an abelian Sylow p-subgroup.
Proof. As p > 2k−1 ≥ 2t−1, where t is the rank of P , we may apply Theorem 2.4. Then
either the result follows or PG is permutation isomorphic to a direct product of cyclic
groups and doubly-transitive nonabelian simple groups with the canonical action, with the
number of factors in the direct product equal to t. As if H is doubly-transitive of degree
n, then H(2) = Sn and a regular group is 2-closed, by [19] (this result also appears in [7,
Theorem 5.1]), we have that (PG)(2) ≤ G(2) = G is a direct product of cyclic groups and
symmetric groups. If any of these symmetric groups are of composite degree, then clearly
a Sylow p-subgroup of (PG)(2) cannot be abelian, as a Sylow p-subgroup of Spi , i ≥ 2,
is nonabelian. Thus G is a direct product of cyclic groups and symmetric groups of prime
degree, and the result follows.
The following result counts the number of Cayley digraphs of G whose automorphism
group does not contain a regular Sylow p-subgroup. That is, it counts the number of Cayley
digraphs of an abelian group for which the previous result does not apply.
Lemma 2.7. Let G be an abelian group of prime-power order pk. Then there are at most
|Aut(Zkp)| · 22p
k−1−pk−2 Cayley digraphs Γ of G such that a Sylow p-subgroup of Aut(Γ)
is not GL.
Proof. IfGL is not a Sylow p-subgroup of Aut(Γ), thenNAut(Γ)(GL) contains an element
of order p that is not in GL by a Sylow Theorem. As NSG(GL) = Aut(G) · GL [8,
Corollary 4.2B], we conclude that Aut(Γ) contains an element α of order p that is also an
element of Aut(G). By Lemma 1.3, we have that α has at most 2pk−1 − pk−2 orbits. As
α ∈ Aut(Γ) if and only if the connection set of Γ is a union of orbits of α, we conclude that
there are at most 22p
k−1−pk−2 Cayley digraphs of G whose automorphism group contains
α. By Lemma 1.4, |Aut(G)| ≤ |Aut(Zkp)|, and so there are at most |Aut(Zkp)| choices for
α. The result then follows.
206 Ars Math. Contemp. 3 (2010) 201–214
Lemma 2.8. Let P be an abelian group of order pk. The number of Cayley digraphs of P
whose automorphism group has Sylow p-subgroup P and contains a subgroup permutation
isomorphic to Sp × A, where A ≤ Spk−1 has an abelian Sylow p-subgroup, is at most
|Aut(P )| · 22pk−1 ≤ |Aut(Zkp)| · 22p
k−1
.
Proof. Assume for the moment that P = Zp × P1, where P1 is an abelian group of order
pk−1. Let a ∈ Z∗p be of order p − 1 and α : Zp × P1 → Zp × P1 by α(i, j) = (ai, j).
Then α ∈ Aut(P ) and α ∈ Sp × A. We conclude that if Γ is a Cayley digraph of P with
connection set S such that Aut(Γ) ≥ Sp × A, then S is a union of orbits of α. As α has
2pk−1 orbits, there are at most 22p
k−1
Cayley digraphs of P whose automorphism group
contains Sp×A, whereA ≤ Spk−1 has an abelian Sylow p-subgroup. Now let Γ be a Cayley
digraph of P whose automorphism group contains a subgroup permutation isomorphic to
Sp ×A, A ≤ Spk−1 with an abelian Sylow p-subgroup. Then there exists (see [8, Exercise
1.6.1]) g ∈ Spk such that g−1Aut(Γ)g ≥ Sp × A. Then Aut(g−1(Γ)) ≥ Sp × A. We
also note that g−1(Γ) is a Cayley digraph of P as P ≤ Sp × A [25]. As P is a Sylow p-
subgroup of Aut(Γ), we have by [2, Lemma 3.1] and a Sylow Theorem that there exists β ∈
Aut(P ) such that β(Γ) = g−1(Γ). We conclude that βAut(Γ)β−1 = Aut(g−1(Γ)) or that
Aut(Γ) ≥ β−1(Sp×A)β. Thus if Γ is a Cayley digraph of P whose automorphism group
contains a subgroup permutation isomorphic to Sp ×A, then Γ is the image under a group
automorphism of P of a Cayley digraph of P whose automorphism group contains Sp×A.
As there are at most 22p
k−1
Cayley digraphs of P whose automorphism group contains
Sp × A, there are at most |Aut(P )| · 22p
k−1
Cayley digraphs of P whose automorphism
group contains a subgroup permutation isomorphic to Sp × A. The result then follows by
Lemma 1.4.
Theorem 2.9. Let G be an abelian group of prime-power order pk. Then almost every
Cayley digraph of G that is not a DRR is a normal Cayley digraph of G. In particular,
lim
p→∞
|NorCayDi(G)−DRR(G)|
|CayDi(G)−DRR(G)|
= 1.
Proof. Choose p so that p ≥ 2k−1. Then, according to Lemma 2.6, if Γ is a non-normal
Cayley digraph of G, then either GL is not a Sylow p-subgroup of Aut(Γ), or Aut(Γ)
contains a subgroup isomorphic to Sp × A, where A ≤ Spk−1 has an abelian Sylow p-
subgroup. Let ι ∈ Aut(G) be given by ι(i, j) = (−i,−j). Note that ι has 1 orbit of size
1 and (pk − 1)/2 orbits of size 2. Thus ι has (pk + 1)/2 orbits. As ι ∈ Aut(G) and fixes
(0, 0), if Γ is a Cayley digraph of G with connection set S, then ι ∈ Aut(Γ) if and only if
ι(S) = S. Thus ι ∈ Aut(Γ) if and only if S is a union of orbits of ι. We conclude that
there are at least 2(p
k+1)/2 distinct Cayley digraphs of G that are not DRR’s of G.
By Lemma 2.8, there are at most |Aut(Zkp)| · 22p
k−1
Cayley digraphs of P whose
automorphism group is permutation isomorphic to Sp × A. As by Lemma 2.7 there are
at most |Aut(Zkp)| · 2p
k−1−pk−2 Cayley digraphs Γ of G such that GL is not a Sylow p-
subgroup of G, we conclude by Lemma 2.6 that there are at most
|Aut(Zkp)|(22p
k−1
+ 2p
k−1−pk−2)
Cayley digraphs of G that are not normal Cayley digraphs of G. Then
E. Dobson: Asymptotic automorphism groups of Cayley digraphs. . . 207
lim
p→∞
|NorCayDi(G)|
|CayDi(G)−DRR(G)|
≥ 1− lim
p→∞
|Aut(Zkp)|(22p
k−1
+ 2p
k−1−pk−2)
2(pk+1)/2
≥ 1− lim
p→∞
2p
k/8(22p
k−1
+ 2p
k−1−pk−2)
2(pk+1)/2
= 1
by Lemma 1.5.
We remark that the above argument also shows that almost every Cayley graph of an
abelian group of prime-power order is a normal Cayley graph of G. Indeed, if there are at
most
|Aut(Zkp)|(22p
k−1
+ 2p
k−1−pk−2)
Cayley digraphs of G that are not normal Cayley digraphs of G, there are at most the same
number of Cayley graphs of G that are not normal Cayley graphs of G. Also, 2(p
k+1)/2 is
the number of Cayley graphs of G, and so
lim
p→∞
|NorCay(G)|
|Cay(G)|
= 1.
3 Almost all Cayley graphs have automorphism group as small as pos-
sible
We begin with a technical result which will allow us to determine an upper bound on the
number of Cayley graphs of abelian groups of prime-power order whose automorphism
groups are not as small as possible.
Lemma 3.1. Let G be an abelian group of odd prime-power order pk, p a prime, and
β ∈ Aut(G) be given by β(i) = −i. Let α ∈ Aut(G) such that α 6= β. Then 〈α, β〉 has at
most 1 + pk−1/2 + pk/4 orbits. If |α| = r is relatively prime to 2, then 〈α, β〉 has at most
1 + pk−1/2 + (pk − pk−1)/(2r′) orbits, where r′ is the smallest divisor of r greater than
one.
Proof. First observe that β has exactly one orbit of one element, and (pk − 1)/2 orbits of
size 2. Additionally, α commutes with β, as, writing the group operation multiplicatively,
αβ(i) = α(i−1) = α−1(i) = βα(i). We conclude that every orbit of 〈α, β〉 has order
dividing |〈α, β〉| which divides |α| · |β|. Clearly 〈α, β〉 has only one orbit of size 1 as β
only has one orbit of size 1. Let O be a nontrivial orbit of 〈α, β〉. Then β|O has order 2,
and so |O| = 2, or |〈α, β〉|O| ≥ 4. If |O| = 2, then α|O ∈ 〈β〉|O. Thus every element of
O is a fixed point of α or for every i ∈ O, α(i) = β(i). Thus every element ofO is either a
fixed point of α or a fixed point of αβ−1. As the set of fixed points of an automorphism of
G forms a subgroup of G, each of α and αβ−1 has at most pk−1 fixed points, and so there
are at most 2pk−1 elements of G that are contained in orbits of 〈α, β〉 of order 2 (actually,
there are fewer, as the identity in G is counted among these 2pk−1 points as it is a fixed
point of both β and αβ−1). There are thus at most pk − 2pk−1 elements in G that are
contained in orbits of size at least 4. Then G has at most 1 + 2pk−1/2 + (pk − 2pk)/4 =
208 Ars Math. Contemp. 3 (2010) 201–214
1 + pk−1/2 + pk/4 orbits. As |α| = r 6= 2, as above, 〈α, β〉 has one orbit of size one.
Also, α has at most pk−1 fixed points, and so there are at most pk−1/2 orbits of size 2.
By arguments analogous to those above, every other point is contained in orbits of size
2r′′ > 1, where r′′ is a divisor of r. Thus if r′ is the smallest divisor of r greater than
one, then there are at most (pk − pk−1)/(2r′) such orbits. As |α| = r 6= 2, α has at most
1 + pk−1/2 + (pk − pk−1)/(2r′) orbits.
We remark that if r = p in the previous result, then 1 + pk−1/2 + (pk − pk−1)/2r =
1 + pk−1 − pk−2/2.
Definition 3.2. Let G be an abelian group that is not an elementary abelian 2-group. We
define Small(G) to be the set of all Cayley graphs Γ of G such that |Aut(Γ)| = 2 · |G|.
That is, Small(G) is the set of all Cayley graphs of G whose automorphism groups are as
small as possible.
Theorem 3.3. Let G be an abelian group of prime-power order. Then almost every Cayley
graph of G has automorphism group of order 2 · |G|. More specifically,
lim
p→∞
|Small(G)|
|Cay(G)|
= 1.
Proof. Let Γ be a Cayley graph of G, where G is an abelian group of prime-power order
pk, p ≥ 3 a prime. As Γ is a graph, the map β ∈ Aut(G) given by β(i) = −i is contained
in Aut(Γ). As |β| = 2 and has exactly one fixed point, there are (pk + 1)/2 orbits of
β and so there are 2(p
k+1)/2 Cayley graphs of G. If a Sylow p-subgroup of Aut(Γ) has
order at least pk+1, then by a Sylow Theorem, NAut(Γ)(GL) has order at least pk+1. As
NSG(GL) = Aut(G) · GL, we have that Aut(Γ) contains an automorphism α 6= β. If
a Sylow p-subgroup of Aut(Γ) has order pk, then by Lemma 2.6, we have that either
Γ ∈ Small(G), there exists β 6= α ∈ Aut(Γ) ∩ Aut(G), or Aut(Γ) ≥ Sp × A, where
A ≤ Spk−1 has Sylow p-subgroup of order pk−1. Note that if Aut(Γ) ≥ Sp × A, then
Aut(Γ) contains an element β 6= α ∈ Aut(Γ) ∩ Aut(G) as p ≥ 3. Thus if Γ is a Cayley
graph of G, then Γ ∈ Small(G) or there exists β 6= α ∈ Aut(Γ) ∩Aut(G).
In the latter case, by Lemma 3.1, 〈α, β〉 has at most 1 + pk−1/2 + pk/4 orbits. As
〈α, β〉 ≤ Aut(G), 〈α, β〉 ≤ Aut(Γ) if and only if the connection set of Γ is a union of
orbits of 〈α, β〉. We conclude that there are at most 21+pk−1/2+pk/4 Cayley graphs of G
whose automorphism group contains 〈α, β〉. By Lemma 1.2, there are at most |Aut(Zkp)|
choices for α, so there are at most |Aut(Zkp)| · 21+p
k−1/2+pk/4 Cayley graphs of G that are
not in Small(G). By Lemma 1.5
lim
p→∞
|Small(G)|
|Cay(G)|
≥ 1− lim
p→∞
|Aut(Zkp)| · 21+p
k−1/2+pk/4
2(pk+1)/2
≥ 1− lim
p→∞
2p
k/8 · 21+pk−1/2+pk/4
2(pk+1)/2
= 1− 0 = 1
The following lemma will allow us to find a lower bound on the number of Cayley
graphs of G that are not in Small(G).
E. Dobson: Asymptotic automorphism groups of Cayley digraphs. . . 209
Lemma 3.4. Let p be an odd prime, and G be an abelian group of prime-power order pk
such that G = Zp` × Gpm , where 1 ≤ ` < k and Gpm is an abelian group of order pm,
` + m = k. Define ι1, ι2 : G → G by ι1(i, j) = (−i, j) and ι2(i, j) = (i,−j). Then
〈ι1, ι2〉 has (2pk + 3pm + 3p`)/8 orbits.
Proof. Clearly (0Z
p`
, 0Gpm ) is an orbit of 〈ι1, ι2〉 of length 1. Also, if r 6= 0 and s 6= 0,
then the orbit of 〈ι1, ι2〉 that contains (r, s) is {(r, s), (−r, s), (r,−s), (−r,−s)}. Clearly
the orbit of 〈ι1, ι2〉 that contains (0, s), s 6= 0, is {(0, s), (0,−s)} and the orbit of 〈ι1, ι2〉
that contains (r, 0), r 6= 0, is {(r, 0), (−r, 0)}. As every orbit of 〈ι1, ι2〉 has orbits of length
1, 2, or 4, we conclude that 〈ι1, ι2〉 has one orbit of length 1, (p`−1)/2+(pm−1)/2 orbits
of size 2, and (pk − (p` − 1)/2 − (pm − 1)/2 − 1)/4 orbits of length 4. Summing the
number of orbits of length 1, 2, and 4, the result follows.
Theorem 3.5. Let G be an abelian group of prime-power order pk. Then almost every
Cayley graph of G whose automorphism group is not of order 2 · |G| is a normal Cayley
graph of G. In particular,
lim
p→∞
|NorCay(G)− Small(G)|
|Cay(G)− Small(G)|
= 1.
Proof. Let p ≥ 3. First suppose that G is not cyclic, with G = Zp` ×Gpm , where Gpm is
an abelian group of order pm and `+m = k. Defining ι1 and ι2 as in the previous lemma,
we see that ι1ι2 ∈ Aut(Γ) for every Cayley graph of G. Applying Lemma 3.4, there
are 2(2p
k+3pm+3p`)/8 Cayley graphs of G whose automorphism group contains 〈ι1, ι2〉, so
there are at least 2(2p
k+3pm+3p`)/8 Cayley graphs of G that are not in Small(G). Clearly
the number of Cayley graphs of G whose automorphism group does not contain a regular
Sylow p-subgroup is at most the number of Cayley digraphs of G whose automorphism
group does not contain a regular Sylow p-subgroup. By Lemma 2.7, we conclude that
there are at most |Aut(Zkp)| · 22p
k−1−pk−2 Cayley graphs of G whose automorphism group
does not contain a regular Sylow p-subgroup. By Lemma 2.6, any Cayley graph ofGwhose
automorphism group has GL as a Sylow p-subgroup and is not a normal Cayley graph of
G must have automorphism group containing a normal subgroup permutation isomorphic
to Sp × A, where A ≤ Spk−1 has an abelian Sylow p-subgroup. By Lemma 2.8, there are
at most |Aut(Zkp)| · 22p
k−1
such Cayley graphs of G. We then have that
lim
p→∞
|NorCay(G)|
|Cay(G)− Small(G)|
≥ 1− lim
p→∞
|Aut(Zkp)| · (22p
k−1−pk−2 + 22p
k−1
)
2(2pk+3pm+3p`)/8
≥ 1− lim
p→∞
2p
k/8 · (22pk−1−pk−2 + 22pk−1)
2(2pk+3pm+3p`)/8
= 1
by Lemma 1.5. Thus the result follows unless G is cyclic.
If G is cyclic, then first note that the result follows if k = 1, as then either Aut(Γ) <
AGL(1, p) or Aut(Γ) = Sp by [1], and so there are only two non-normal Cayley graphs
of the abelian group of prime order, namely Kp or its complement. For k ≥ 2, observe
that by Lemma 2.6, a Cayley graph Γ of G is either normal or has a Sylow p-subgroup that
is not regular, as it is not possible for Aut(Γ) to contain a subgroup of the form Sp × A
as Sp × A does not have a regular cyclic subgroup, A ≤ Spk−1 with a regular Sylow
210 Ars Math. Contemp. 3 (2010) 201–214
p-subgroup. If a Sylow p-subgroup of Aut(Γ) is not (Zpk)L, then as usual there exists
α ∈ Aut(Zpk) such that α has order p and is contained in Aut(Γ). As we may assume that
p 6= 2, Aut(Zpk) = Z∗pk is cyclic, and so Aut(Zpk) contains a unique element α of order
p. It is straightforward to verify that α(x) = (1 + pk−1)x, and that α has pk−1 orbits of
order 1, and (pk − pk−1)/p orbits of size p. As ι : Zpk → Zpk given by ι(x) = −x is
contained in Aut(Zpk) and Aut(Γ), ι has one orbit of size 1 and (pk − 1)/2 orbits of size
2, and Z∗pk is cyclic, we have that ια has one orbit of size 1, (p
k−1 − 1)/2 orbits of size
2, and (pk − pk−1)/2p orbits of size 2p. Then ια has pk−1 + (1− pk−2)/2 orbits, and so
there are at most 2p
k−1+(1−pk−2)/2 non-normal Cayley graphs of Zpk , p an odd prime and
k ≥ 2.
Now, let b ∈ Z∗pk be of order p − 1, and β : Zpk → Zpk by β(x) = bx. Note that
ι ∈ 〈β〉. If βa(x) = x for a ≥ 1, and x 6= 0, then bax ≡ x (mod pk) or equivalently,
(ba − 1)x ≡ 0 (mod pk). Then ba − 1 ≡ 0 (mod p) so that ba = 1 + rp for some positive
integer r. Then ba has order a power of p and as |b| = p − 1, we must have that ba = 1
or, equivalently, a is a multiple of p − 1. We conclude that if x 6= 0, then the orbit of 〈β〉
that contains x has length p − 1, and that β has 1 + (pk − 1)/(p − 1) orbits. Thus there
are 21+(p
k−1)/(p−1) Cayley graphs of Zpk whose automorphism group contains β, and so
there are at least 21+(p
k−1)/(p−1) Cayley graphs of Zpk that are not in Small(G), p ≥ 3.
Note that as k ≥ 2, (pk − 1)/(p− 1) 6= 1. Then
lim
p→∞
|NorCay(G)|
|Cay(G)− Small(G)|
≥ 1− lim
p→∞
2p
k−1+(1−pk−2)/2
21+(pk−1)/(p−1)
= 1.
4 Problems
Conjecture 4.1. Almost every Cayley (di)graph whose automorphism group is not as small
as possible is a normal Cayley (di)graph.
It is difficult to determine the automorphism group of a (di)graph, so the main way to
obtain examples of vertex-transitive graphs is to construct them. An obvious construction
is that of a Cayley (di)graph, and the conjecture of Imrich, Lovász, Babai, and Godsil
says that when performing this construction, additional automorphism are almost never
obtained. The obvious way of constructing a Cayley (di)graph of G that does not have
automorphism group as small as possible is to choose an automorphism α of G and make
the connection set a union of orbits of α. The above conjecture in some sense says that
this construction almost never yields additional automorphisms other than the ones given
by the construction.
There are two additional families of (di)graphs that can be considered, namely “semi-
wreath products” and “deleted wreath products” - such graphs are not normal Cayley graphs
provided p 6= 2. Before turning to these families, we define the wreath product of two di-
graphs.
Definition 4.2. Let Γ1 and Γ2 be digraphs. Define the wreath product of Γ1 and Γ2, de-
noted Γ1 oΓ2, to be the graph with vertex set V (Γ1)×V (Γ2) and edges set {(g, h1)(g, h2) :
h1h2 ∈ E(Γ2)} ∪ {(g1, h1)(g2, h2) : g1g2 ∈ E(Γ1), h1, h2 ∈ V (Γ2)}. We say the wreath
product is trivial if |V (Γ1)| = 1 or |V (Γ2)| = 1.
E. Dobson: Asymptotic automorphism groups of Cayley digraphs. . . 211
If Γ is a Cayley digraph of an abelian group with connection set S, and Γ = Γ1 o Γ2,
where Γ1 is a Cayley digraph of an abelian group G1 and Γ2 is a Cayley digraph of an
abelian group G2, then S −G2 is a union of cosets of G2.
Definition 4.3. A Cayley graph Γ of an abelian group G is a semiwreath product if there
exist subgroups H ≤ K < G such that S −K is a union of cosets of H . We say that the
semiwreath product is trivial if H = 1.
Thus ifH = K, a semiwreath product is in fact a wreath product. One other comment is
in order about semiwreath products. That is, it is unclear what the operands of a semiwreath
product are (i.e. as defined it is not really a product). The term is used though, as many
researchers refer to such graphs in this way (even if only speaking informally) as they are
in some sense “almost” wreath products.
Definition 4.4. A Cayley graph Γ of an abelian group G is a deleted wreath product if
Γ = (Γ1 o K̄m) −mΓ1, where Γ1 is a Cayley graph of an abelian group of order |G|/m,
and mΓ1 is m vertex-disjoint copies of Γ1.
We remark that the above definition of a semiwreath product may not be the best possi-
ble choice to capture the idea behind “semiwreath” digraphs, as the classes of semiwreath
digraphs and deleted wreath products, as defined, are not disjoint. For example, the com-
plete graph is contained in both classes, and there are other, more complicated examples
that are also in both classes.
As is somewhat standard, we will refer to a Cayley (di)graph of a cyclic group of
order n as a circulant (di)graph of order n. Baik, Feng, Song, and Xu made the following
conjecture in 1998 [6]:
Conjecture 4.5. All connected circulant graphs of order n are normal except for a com-
plete graph, a wreath product of two smaller graphs, or a deleted wreath product.
It is easy to see that this conjecture is not strictly true. Let Cq be a cycle of prime length
q and Kp a complete graph of prime order p 6= q. Then Γ = Cq oKp − pCq is a deleted
wreath product. Using [20] or the somewhat more accessible [9, Theorem 3.1], it is not
difficult to see that Aut(Γ) = Dq × Sp, where Dq is the dihedral group of order 2q. But
then Γ̄, the complement of Γ, is neither a wreath product, nor a deleted wreath product,
but if p ≥ 5 then Γ̄ is not a normal circulant graph and is certainly connected. This is not,
though, a serious defect in the conjecture, as if all of the above conjectured automorphism
groups were written down, Aut(Γ̄) = Aut(Γ) would certainly be on the list. A more
serious defect of the above conjecture is the following example.
Example 4.6. Let p be an odd prime and Γ the Cayley digraph of Zp3 with connection set
S = {±p,±1,±1 + p2,±1 + 2p2, . . . ,±1 + (p− 1)p2}. Then Γ is a semiwreath circulant
graph and is not isomorphic to a wreath product of two nontrivial graphs.
Proof. Clearly Γ is a semiwreath circulant graph with K the unique subgroup of Zp3 of
order p2, that is, K = 〈p〉, and H the unique subgroup of Zp3 of order p, that is H = 〈p2〉.
We show that Γ is not isomorphic to a wreath product of two nontrivial graphs by showing
that Aut(Γ) = 〈ι, τ, τp2 |B : B ∈ B〉, where ι, τ : Zp3 → Zp3 by ι(i) = −i, τ(i) = i+ 1,
and B is the complete block system of 〈τ〉 formed by the orbits of 〈τp〉 (so the orbits of 〈τ〉
are just the cosets of K). Then Aut(Γ) cannot be written as a nontrivial wreath product of
212 Ars Math. Contemp. 3 (2010) 201–214
two groups, and so by [12, Theorem 5.7], Γ cannot be written as a wreath product of two
nontrivial graphs.
Note that Aut(Γ) is clearly not a complete graph or its complement, so Aut(Γ) is
not doubly-transitive. As Zp3 is a Burnside group [8, Theorem 3.5A], we must have that
Aut(Γ) is imprimitive, admitting a nontrivial complete block system C. By [26, Exercise
6.5], we have that C is either formed by the orbits of 〈τp2〉 or 〈τp〉. If C is formed by
the orbits of 〈τp2〉 (and so consists of p2 blocks of size p), then the quotient graph Γ/C
defined by V (Γ/C) = C and C1C2 ∈ E(Γ/C) if and only if some vertex of C1 is adjacent
to some vertex of C2 is isomorphic to the circulant graph of order p2 with connection
set T = {±p,±1}. Using [13, Theorem 15], it is easy to verify that Γ/C is a normal
circulant graph of order p2, and so Aut(Γ)/C contains a normal regular cyclic subgroup.
We conclude in this case that Aut(Γ) admits a complete block system consisting of p
blocks of size p2, necessarily formed by the orbits of 〈τp〉. It thus suffices to only consider
the case where C = B.
If C = B, then observe that Γ[B] is a p2-cycle, and so has automorphism group Dp2 .
Then StabAut(Γ)(B)|B ≤ Dp2 , and so by [8, Exercise 1.5.10] we see that Aut(Γ) also
admits a complete block system D consisting of p2 blocks of size p, necessarily formed
by the orbits of 〈τp2〉. As above, Γ/D is the circulant digraph of order p2 with connection
set {±p,±1}. It follows by [13, Theorem 15] (as Γ cannot be written as a nontrivial
wreath product as it is 4-regular and p > 2), that Aut(Γ/D) ≤ {x → ax + b : a ∈
Z∗p2 , b ∈ Zp2}. As the only a ∈ Z∗p2 such that a{±p,±1} = {±p,±1} is a = ±1
and x → ax is an automorphism of Γ/D if and only if a{±p,±1} = {±p,±1}, we
see that Aut(Γ/D) ∼= Dp2 . Thus Aut(Γ)/D = Dp2 as ι ∈ Aut(Γ) as Γ is a circulant
graph. As Aut(Γ)/D = Dp2 and StabAut(Γ)(B)|B ≤ Dp2 , it must be the case that
StabAut(Γ)(B)|B = Zp2 as an involution in StabAut(Γ)(B)|B cannot be mapped to ι/D
by the map g → g/D as ι/B 6= 1. We conclude that Aut(Γ) ≤ 〈ι, τ, τp2 |B : B ∈ B〉. It is
not difficult to see that 〈τ, τp2 |B : B ∈ B〉 ≤ Aut(Γ), and then the result follows.
We believe that the two types of counterexamples to the Conjecture 4.5 are the only
possible counterexamples for Cayley (di)graphs of abelian groups. We make the following
conjecture, which would be quite useful in verifying Conjecture 4.1.
Conjecture 4.7. Let Γ be a Cayley (di)graph of an abelian group G. Then one of the
following is true:
• Γ is a normal Cayley (di)graph of G,
• Γ is a semiwreath product, or
• the automorphism group of Γ is same as the automorphism group of a deleted wreath
product.
It it not overly difficult to show using [23, Theorem 2.3] (this result is basically a trans-
lation of work done on Schur rings [14, 21, 22] into the language of group theory, and this
result was independently obtained in [11] for the special case of circulants of square-free
order) that the preceding conjecture is true provided that G is cyclic, and so the two types
of counterexamples to Conjecture 4.5 presented above are indeed the only possible types
of counterexamples provided that G is cyclic. We remark that the preceding conjecture is
known to be false for some nonabelian groups, as for some such groups it is possible for
E. Dobson: Asymptotic automorphism groups of Cayley digraphs. . . 213
a Cayley (di)graph to have an almost simple simply primitive automorphism group (see
[24]).
Finally, we would like to finish with an additional problem.
Problem 4.8. For an abelian group G, does there exist a natural collection F of families of
Cayley (di)graphs of G and a partial order on F such that every Cayley (di)graph of G is
contained in some element ofF and if F1  F2 and there is no F3 such that F1  F3  F2,
then almost every Cayley (di)graph of G that is not in F1 is in F2?
5 Acknowledgement
The author is indebted, as usual, to the anonymous referees for their careful reading of this
manuscript, and their thoughtful suggestions for improvement. The manuscript is much
improved thanks to their efforts.
References
[1] B. Alspach, Point-symmetric graphs and digraphs of prime order and transitive permutation
groups of prime degree, J. Combinatorial Theory Ser. B 15 (1973), 12–17.
[2] L. Babai, Isomorphism problem for a class of point-symmetric structures, Acta Math. Acad.
Sci. Hungar. 29 (1977), 329–336.
[3] L. Babai, Infinite digraphs with given regular automorphism groups, J. Combin. Theory Ser. B
25 (1978), 26–46.
[4] L. Babai, Finite digraphs with given regular automorphism groups, Period. Math. Hungar. 11
(1980), 257–270.
[5] L. Babai and C. D. Godsil, On the automorphism groups of almost all Cayley graphs, European
J. Combin. 3 (1982), 9–15.
[6] Y.-G. Baik, Y. Feng, H.-S. Sim and M. Xu, On the normality of Cayley graphs of abelian
groups, Algebra Colloq. 5 (1998), 297–304.
[7] P. J. Cameron, M. Giudici, G. A. Jones, W. M. Kantor, M. H. Klin, D. Marušič and L. A.
Nowitz, Transitive permutation groups without semiregular subgroups, J. London Math. Soc.
66 (2002), 325–333.
[8] J. D. Dixon and B. Mortimer, Permutation groups, Vol. 163 of Graduate Texts in Mathematics,
Springer-Verlag, New York, 1996.
[9] E. Dobson, On the proof of a theorem of Pálfy, Electron. J. Combin. 13 (2006), #16.
[10] E. Dobson, On overgroups of regular abelian p-groups, Ars Math. Contemp. 2 (2009), 59–76.
[11] E. Dobson and J. Morris, On automorphism groups of circulant digraphs of square-free order,
Discrete Math. 299 (2005), 79–98.
[12] E. Dobson and J. Morris, Automorphism groups of wreath product digraphs, Electron. J. Com-
bin. 16 (2009), #17.
[13] E. Dobson and D. Witte, Transitive permutation groups of prime-squared degree, J. Algebraic
Combin. 16 (2002), 43–69.
[14] S. A. Evdokimov and I. N. Ponomarenko, Characterization of cyclotomic schemes and normal
Schur rings over a cyclic group, Algebra i Analiz 14 (2002), 11–55.
[15] C. D. Godsil, On the full automorphism group of a graph, Combinatorica 1 (1981), 243–256.
214 Ars Math. Contemp. 3 (2010) 201–214
[16] C. D. Godsil, GRRs for nonsolvable groups, in: Algebraic methods in graph theory, Vol. I, II
(Szeged, 1978), Vol. 25 of Colloq. Math. Soc. János Bolyai, North-Holland, Amsterdam, 1981,
221–239.
[17] D. Gorenstein, Finite groups, Harper & Row Publishers, New York, 1968.
[18] B. Huppert, Endliche Gruppen. I, Die Grundlehren der Mathematischen Wissenschaften, Band
134, Springer-Verlag, Berlin, 1967.
[19] L. A. Kalužnin and M. H. Klin, Some numerical invariants of permutation groups, Latviı̆sk.
Mat. Ežegodnik (Vyp. 18) (1976), 81–99.
[20] M. H. Klin and R. Pöschel, The König problem, the isomorphism problem for cyclic graphs and
the method of Schur rings, in: Algebraic methods in graph theory, Vol. I, II (Szeged, 1978),
Vol. 25 of Colloq. Math. Soc. János Bolyai, North-Holland, Amsterdam, 1981, 405–434.
[21] K. H. Leung, S. H. Man, On Schur rings over cyclic groups. II, J. Algebra 183 (1996), 273–285.
[22] K. H. Leung and S. H. Man, On Schur rings over cyclic groups, Israel J. Math. 106 (1998),
251–267.
[23] C. H. Li, Permutation groups with a cyclic regular subgroup and arc transitive circulants, J.
Algebraic Combin. 21 (2005), 131–136.
[24] D. Marušič, R. Scapellato, Classifying vertex-transitive graphs whose order is a product of two
primes, Combinatorica 14 (1994), 187–201.
[25] G. Sabidussi, Vertex-transitive graphs, Monatsh. Math. 68 (1964), 426–438.
[26] H. Wielandt, Finite permutation groups, Translated from the German by R. Bercov, Academic
Press, New York, 1964.
[27] M.-Y. Xu, Automorphism groups and isomorphisms of Cayley digraphs, Discrete Math. 182
(1998), 309–319.