MOST RIGID REPRESENTATIONS AND CAYLEY INDEX

arXiv:1703.09299v1 [math.CO] 27 Mar 2017

JOY MORRIS AND JOSH TYMBURSKI
Abstract. For any finite group G, a natural question to ask is the order of the smallest
possible automorphism group for a Cayley graph on G. A particular Cayley graph whose
automorphism group has this order is referred to as an MRR (Most Rigid Representation),
and its Cayley index is a numerical indicator of this value. Study of GRRs showed that
with the exception of two infinite families and seven individual groups, every group admits
a Cayley graph whose MRR is a GRR, so that the Cayley index is 1. The full answer to
the question of finding the smallest possible Cayley index for a Cayley graph on a fixed
group was almost completed in previous work, but the precise answers for some finite
groups and one infinite family of groups were left open. We fill in the remaining gaps to
completely answer this question.

1. Introduction
All groups and graphs in this paper are finite. All of our graphs are simple, undirected,
and have no loops.
A Cayley graph Γ = Cay(G, S) where S ⊆ G with S = S −1 and 1 ∈
/ S, is the graph whose
vertices are the elements of G, with (g, gs) ∈ E(Γ) if and only if g ∈ G and s ∈ S. We
refer to S as the connection set for Γ. Let A = Aut(Γ). Observe that LG , the left-regular
representation of G, lies in A, so |G| divides |A|.
Definition 1.1. The Cayley index c(Γ) of the Cayley graph Γ = Cay(G, S), is |A : LG |.
The Cayley index c(G) of the group G is minS⊆G,S=S −1 c(Cay(G, S)); that is, the lowest
Cayley index of any Cayley graph on the group G.
Definition 1.2. A Cayley graph Γ = Cay(G, S) is a GRR (Graphical Regular Representation) for G if c(Γ) = 1.
Thus, groups that admit GRRs are precisely the groups whose Cayley index is 1. In
order to completely characterise these groups, we require another definition.
Definition 1.3. Let A be an abelian group of even order, and y an involution in A. Then
the generalised dicyclic group Dic(A, y, x) is hA, xi where x ∈
/ A, x2 = y, and x−1 ax = a−1
for every a ∈ A.
The study of GRRs involved many researchers and papers. Some of the most influential
work along the way appeared in [5, 6, 7]. Watkins [12] observed that there are two infinite
families of graphs that cannot admit GRRs: generalised dicyclic groups, and abelian groups
that are not elementary abelian 2-groups. Determining groups that admit GRRs was
2010 Mathematics Subject Classification. Primary 05C25.
1

completed by Hetzel [4] and Godsil [3]. Hetzel proved that aside from the two infinite
families noted by Watkins, there are exactly 13 small solvable groups (of order at most 32)
that do not admit a GRR. Godsil showed that every non-solvable group admits a GRR.
In the case where a group fails to admit a GRR, a natural question to ask is: what is the
Cayley index of the group, and what is a Cayley graph on the group that has that Cayley
index? The following terminology was coined in [8].
Definition 1.4. Let G be a group with c(G) > 1, and let Γ = Cay(G, S) be a Cayley
graph on G with c(Γ) = c(G). Then we say that Γ is an MRR (Most Rigid Representation)
for G.
The bulk of this paper is divided into 4 sections. In Section 2, we describe the groups that
do not admit a GRR but do not lie in either of the infinite families of groups that do not
admit a GRR. For each of these groups, we find its Cayley index and an MRR. In Section 3,
we find the Cayley index of every abelian group, and find MRRs for those groups whose
Cayley index is greater than 2. In Section 4, we consider a subfamily of generalised dicyclic
groups (specifically, the hamiltonian 2-groups), and show that the smallest two of these
have Cayley index 16, while the rest have Cayley index 8. Finally, in Section 5, we find
the Cayley index for every generalised dicyclic group that was not included in Section 4.
Much of the work that we summarise in this paper was done in [8], but they left some
gaps. Our paper fills all of these gaps, thus completing their work. Specifically, we fill
the following gaps in their work. We examine the Cayley indices of the groups that do
not lie in either of the infinite families; we give the Cayley indices for the four abelian
groups for which they did not specify it (although they stated that these had been found
by computer); we find the precise Cayley index for generalised dicyclic groups of order at
most 96 (they bounded almost all of these by 4, but most in fact have Cayley index 2);
and we find the Cayley indices for all hamiltonian 2-groups (they bounded these by 16,
but almost all have Cayley index 8). Table 1 summarises this work, providing the Cayley
index for every finite group.
For a number of the small individual groups, we found MRRs using Sage [11] and its
GAP package [2]. The Cayley index of any of the graphs we present can be easily checked
via computer, using this or other appropriate software.
Throughout this paper, Q8 = {±1, ±i, ±j, ±k} is the usual representation of the quaternion group of order 8. We use D2n for n ≥ 3 to represent the dihedral group of order 2n.
Four of the exceptional groups listed in Theorem 2.1 we denote by Hi for i ∈ {1, 2, 3, 4}; a
precise representation of each of these groups is given in Theorem 2.1.
To represent some of our MRRs, we use cartesian products. For two graphs Γ1 and Γ2 ,
the cartesian product of Γ1 with Γ2 is denoted by Γ1 Γ2 . It is the graph whose vertices
are the elements of V (Γ1 ) × V (Γ2 ), with (u1 , v1 ) adjacent to (u2 , v2 ) if and only if either
u1 = u2 and v1 is adjacent to v2 in Γ2 , or v1 = v2 and u1 is adjacent to u2 in Γ1 . We say
that a graph Γ on more than one vertex is prime with respect to the cartesian product if
Γ∼
= Γ and Γ2−i has just one vertex. It is
= Γ1 Γ2 implies that for some i ∈ {1, 2}, Γi ∼
well-known that every graph has a unique prime factorisation as the cartesian product of
prime graphs. We say that two graphs are relatively prime with respect to the cartesian
2

product if they have no common factors in their prime factorisations. We sometimes simply
refer to the graphs as prime or relatively prime.
Group
Cayley index
See
Abelian groups
Zn2 , n ≥ 5
1
[6], 1.2 of [8]
Z32 , Z4 × Z2
6
Lemma 2.7 of [8]
Z42
8
Table 3
Z24
4
Table 3
2
Z4 × Z2
8
Table 3
Z23
8
Lemma 2.4 of [8]
Z33
12
Table 3
all other abelian groups
2
Theorem 1 of [8]
Hamiltonian 2-groups
Q8
16
Lemma 2.6 of [8]
Q8 × Z2
16
Section 4
Q8 × Zn2 , n ≥ 2
8
Proposition 4.7
Other generalised dicyclic groups
Dic(Z6 , 3, x)
4
Table 4
Dic(Z8 , 4, x)
4
Table 4
Dic(Z4 × Z2 , (0, 1), x)
4
Table 4
all other generalised dicyclic groups
2
Section 5, and Theorem 2 of [8]
Exceptional groups
D6 , D8 , D10
2
Section 2 of [8], or Table 2
A4
2
Table 2
Q8 × Z3 , Q8 × Z4
2
Table 2
H1 of order 16
2
Table 2
H2 of order 16
2
Table 2
H3 of order 18
2
Table 2
H4 of order 27
2
Table 2
Every group not listed above
1
[3]
Table 1. Cayley indices for all finite groups

2. Exceptional groups
We begin by listing the 13 groups that do not admit a GRR but do not lie in either of
the infinite families that do not admit GRRs.
Theorem 2.1 (see [3]). The following are the only groups that are neither generalised
dicyclic nor abelian of exponent greater than 2, yet admit no GRR:
• Z22 , Z32 , Z42 ;
3

• D6 , D8 , D10 where these represent the dihedral group of orders 6, 8, and 10 (respectively);
• A4 , the alternating group of degree 4;
• H1 := ha, b, c : a2 = b2 = c2 = 1, abc = bca = cabi;
• H2 := ha, b : a8 = b2 = 1, bab = a5 i;
• H3 := ha, b, c : a3 = b3 = c2 = 1, ab = ba, (ac)2 = (bc)2 = ei;
• H4 := ha, b, c : a3 = c3 = 1, ac = ca, bc = cb, b−1 ab = aci;
• Q8 × Z3 , Q8 × Z4 , where Q8 is the quaternion group of order 8.
The groups listed in the first bullet are abelian, and their Cayley indices are given
in Section 3.
All of the remaining groups have Cayley index 2. Their Cayley index must be at least
2 by Theorem 2.1, since they admit no GRR. This was shown explicitly in [12, Theorem
2] for the dihedral groups in the second bullet. It was shown in [14, Proposition 3.7] for
A4 . For the groups H1 and H3 , it was shown in [14, Proposition 5.3 and Theorem 2]. The
group H2 was dealt with in [9, Theorem 2 or Proposition 3.1], and H4 in [10, Theorem 3].
Finally, Q8 × Z3 and Q8 × Z4 were addressed in [13, Theorem].
To show that the Cayley index of each is precisely 2, we present Table 2. For each group,
we give the connection set for a Cayley graph on that group that has Cayley index 2. The
Cayley indices of these graphs can be verified by hand or by computer.
Group G
S such that c(Cay(G, S)) = 2
−1
D2n = ha, b : a = b = 1, aba = b i, n ∈ {3, 4, 5}
{a, ab}
A4
{(1 2 3)±1 , (1 2)(3 4)}
H1 = ha, b, c : a2 = b2 = c2 = 1, abc = bca = cabi
{a, b, c, (ab)±1 }
8
2
5
H2 = ha, b : a = b = 1, bab = a i
{a±1 , a±2 , b}
H3 = ha, b, c : a3 = b3 = c2 = 1, ab = ba, (ac)2 = (bc)2 = ei
{a±1 , c, ac, bc}
3
3
−1
±1 ±1
H4 = ha, b, c : a = c = 1, ac = ca, bc = cb, b ab = aci {a , b , (a−1 b)±1 , (bab−1 )±1 }
Q8 × Z3 = hi, j, z : z 3 = 1, iz = zi, jz = zji
{±i, (iz)±1 , (jz)±1 }
4
±1
Q8 × Z4 = hi, j, z : z = 1, iz = zi, jz = zji
{z , ±i, ±j, (iz)±1 , (−kz)±1 }
Table 2. MRRs for exceptional groups
2

n

The MRRs listed in the first line of this table were also mentioned in [8].
3. Abelian groups
The Cayley index of every abelian group was determined in [8]. However, for a small
number of these they stated only that the Cayley index had been found by Hetzel on
computer, and cite a private communication. The known results on abelian groups are as
follows.
Theorem 3.1 (Theorem 1, Lemma 2.4, Lemma 2.7 [8]). The only finite abelian groups
with a Cayley index greater than 2 are:
• Z32 and Z4 × Z2 , for which the Cayley index is 6, with MRR K2 K2 K2 (the cube);
4

• Z23 , for which the Cayley index is 8, with MRR K3 K3 ;
• Z42 , Z4 × Z22 , and Z24 ; and
• Z33 .
In the rest of this section, we list the Cayley index for each of the last four groups
together with an MRR for each group. The Cayley indices for these graphs and the fact
that these are the Cayley indices for these groups can be verified by computer.
If A is an abelian group that we are presenting as being isomorphic to Zi1 × . . . × Zik ,
then we let {z1 , . . . , zk } be the canonical generating set for this group, so |zj | = ij . We
present the Cayley index and an MRR for each group in Table 3.
Group Cayley index
Connection set for an MRR
Z42
8
{z1 , z2 , z3 , z4 , z1 z2 , z1 z3 , z2 z4 }
Z4 × Z22
8
{z1±1 , z2 , z3 , (z1 z2 )±1 , (z1 z3 )±1 }
2
Z4
4
{z1±1 , z2±1 , z12 , (z1 z2 )±1 }
Z33
12
{z1±1 , z2±1 , z3±1 , (z1 z2 )±1 , (z1 z3 )±1 , (z2 z3 )±1 }
Table 3. MRRs for abelian groups not given in [8]
It may seem odd that c(Z42 ) > c(Z32 ). However, Lemma 4.3 does not apply here, because
neither MRR for Z32 (K2 K2 K2 and its complement, K4 K2 ), is relatively prime to K2 ,
which is the unique connected MRR for Z2 .
4. The groups Q8 × Zn2
In this section we deal with a particular family of generalised dicyclic groups: groups
of the form Q8 × Zn2 for some nonnegative integer n. These groups are also known as
hamiltonian 2-groups.
We begin with three important results from [8].
Lemma 4.1 (Lemma 2.6, [8]). The group Q8 has Cayley index 16, with C4 K2 as an
MRR.
Lemma 4.2 (Proposition 2.9, [8]). Every group other than Z22 , Z32 , Z4 , Z4 × Z2 , and Z23
admits a connected MRR that is prime with respect to the cartesian product.
Lemma 4.3 (Lemma 2.8, [8]). Let G1 and G2 be groups having connected MRRs that are
relatively prime with respect to the cartesian product. Then c(G1 × G2 ) ≤ c(G1 )c(G2 ).
In fact, if Γ1 and Γ2 are connected MRRs for G1 and G2 (respectively) that are relatively
prime with respect to the cartesian product, then c(Γ1 Γ2 ) = c(G1 )c(G2 ) and Γ1 Γ2 is a
Cayley graph on G1 × G2 .
The following observation is made in [8] and is implicit in their Theorem 2(b), which
states that c(Q8 × Zn2 ) ≤ 16 for every integer n ≥ 0. It can be deduced from Lemmas 4.1
to 4.3, using the fact that c(Z2 ) = 1.
Corollary 4.4. For every group G ∈
/ {Z22 , Z32 , Z4 , Z4 × Z2 , Z23 }, c(G × Z2 ) ≤ c(G).
5

The following result is key to providing a lower bound for the Cayley index of every
group Q8 × Zn2 .
Proposition 4.5 (Classification Theorem, [1]). There are 8 permutations ϕ of the elements
of G = Q8 × Zn2 that fix the identity, and have the property that for every g, h ∈ G, ϕ(gh)
is either ϕ(g)h, or ϕ(g)h−1 .
Corollary 4.6. The Cayley index of Q8 × Zn2 is at least 8 for every integer n ≥ 0.
Proof. Fix n, and let G = Q8 × Zn2 . Let S be any inverse-closed subset of G, and let
Γ = Cay(G, S). Let ϕ be any of the 8 permutations given in Proposition 4.5. To prove
this result, it will be sufficient to show that ϕ is an automorphism of Γ.
We know that for any g ∈ G, g is adjacent to gs if and only if s ∈ S. We also know
that ϕ(gs) is either ϕ(g)s, or ϕ(g)s−1. Since S is inverse-closed, each of these is adjacent
to ϕ(g) if and only if s ∈ S. Thus, ϕ is indeed an automorphism of Γ.

To complete this section, we note that C4 K2 K2 is an MRR for Q8 × Z2 with Cayley
index 16, verified by computer. However, for Q8 × Z22 , the Cayley index is 8, with MRR
Cay(Q8 × Z22 , {±i, ±j, ±k, ±iz1 , ±kz1 z2 , z1 , z2 }), where z1 and z2 are two distinct central
involutions that do not lie in Q8 .
Thus, using Corollary 4.4 and Corollary 4.6 we are able to conclude the following.
Proposition 4.7. For every integer n ≥ 2, the Cayley index of Q8 × Zn2 is 8.
5. Other Generalised Dicyclic groups
Imrich and Watkins [8] showed that generalised dicyclic groups of order greater than 96
that are not of the form Q8 × Zn2 have Cayley index 2. Many of the ideas from their proof
in fact apply to generalised dicyclic groups of smaller orders. We reproduce these key ideas
here, without their assumptions on order. We generally need to find two elements that
satisfy a number of conditions. We note that the condition a1 6= ya2 was not listed in [8]
but is required; for this reason we provide a full proof of Lemma 5.4.
Definition 5.1. Let Dic(A, y, x) be a generalised dicyclic group. We say that (a1 , a2 ) ∈
A × A is a suitable pair of elements of Dic(A, y, x) if for every {i, j} = {1, 2} we have
(i) a1 6= a2 , ya2
(ii) a2i 6= 1, y;
(iii) ai 6= a2j , ya2j ; and
(iv) a1 a2 6= 1, y.
Lemma 5.2. Let A = hz1 i be a cyclic group of order 2n ≥ 10, and let S = {z1 , z1−1 }. Then
(z1 , z1−2 ) is a suitable pair for D = Dic(A, z1n , x).
Also, if Γ = Cay(D, S ∪ {x, x−1 , xz1 , x−1 z1 , xz1−2 , x−1 z1−2 }) and ϕ ∈ Aut(Γ)1 , then
ϕ(A) = A.
Proof. We have y = z1n . We verify the conditions for (z1 , z1−2 ) to be a suitable pair. Since
n ≥ 5, (i) and (ii) are satisfied; (iii) and (iv) are equally easy to check.
6

It is straightforward to verify that when n > 4, an is the unique vertex that has 6 common
neighbours with 1. In fact, this shows that for any vertex v, vz1n is uniquely determined
as the vertex that has 6 common neighbours with v. Since the neighbours of 1 can be
partitioned into three pairs of this sort ({x, x−1 = xz1n }, {xz1 , xz1n+1 }, and {xz1−2 , xz1n−2 })
and two elements (z1 and z1−1 ) whose match in this respect (z1n+1 , and z1n−1 respectively) is
not a neighbour of 1, it must be the case that {z1 , z1−1 } and {x, x−1 , xz1 , xz1n+1 , xz1−2 , xz1n−2 }
are fixed setwise by ϕ. Repeating this argument shows that ϕ(c) ∈ A for every c ∈ A.
Thus, ϕ(A) = A.

Lemma 5.3. Let A = hz1 , z2 i where |z1 | = 2n ≥ 6, |z2 | = 2, and z1 z2 = z2 z1 , so
A∼
= Z2n × Z2 . Let S = {z1±1 , z2 }. Then (z1 , z1−2 ) is a suitable pair for D = Dic(A, b, x).
Also, if Γ = Cay(D, S ∪ {x, x−1 , xz1 , x−1 z1 , xz1−2 , x−1 z1−2 }) and ϕ ∈ Aut(Γ)1 , then
ϕ(A) = A.
Proof. Checking the conditions for (z1 , z1−2 ) to be a suitable pair is straightforward.
Since z2 ∈ S is central in D and x−1 = xz2 , the following pairs of neighbours of 1 are
adjacent in Γ: {x, x−1 }; {xz1 , x−1 z1 }; {xz1−2 , x−1 z1−2 }. However, z1 , z1−1 and z2 have no
neighbours in S. Thus, we can distinguish the neighbours of 1 that lie in A from the
neighbours of 1 that lie in xA. Repeating this argument shows that ϕ(c) ∈ A for every
c ∈ A. Thus ϕ(A) = A.

Lemma 5.4. Let A be an abelian group that has Cayley index 2, so we can find S such
that ∆ = Cay(A, S) has Cayley index 2. Let D = Dic(A, y, x) be a generalised dicyclic
group with suitable pair (a1 , a2 ). Let
Γ = Cay(D, S ∪ {x, x−1 , xa1 , x−1 a1 , xa2 , x−1 a2 })
and suppose that for every ϕ ∈ Aut(Γ)1 , we have ϕ(A) = A. If ϕ(x) 6= 1, then ϕ(a) = a,
and ϕ(xa) = (xa)−1 for every a ∈ A.
Proof. Throughout this proof, we use NX (v) to denote the neighbours of the vertex v that
lie in the subset X of the vertices of Γ. First we will show that ϕ(x) ∈ {x, x−1 }.
We are assuming that ϕ(A) = A, and need to show that ϕ(x) 6∈ {xa1 , x−1 a1 , xa2 , x−1 a2 }.
Suppose that ϕ(x) ∈
/ {x, x−1 }. By symmetry, without loss of generality we may assume
that ϕ(x) = xa1 .
Since ϕ(A) = A and the induced subgraph on A is ∆ which has Cayley index 2, we
know that we either have ϕ(a) = a for every a ∈ A, or ϕ(a) = a−1 for every a ∈ A. (This
is always the case in a Cayley graph of Cayley index 2 on an abelian group.)
Since ϕ(x) = xa1 , ϕ(xA) = xA, and the induced subgraph on xA is isomorphic to ∆,
we must have either ϕ(xa) = xaa1 for every a ∈ A, or ϕ(xa) = xa−1 a1 for every a ∈ A.
Suppose the first of these possibilities holds, so ϕ(xa1 ) = xa21 , which must therefore be
a neighbour of 1 in xA, and hence an element of
NxA (1) = {x, x−1 , xa1 , x−1 a1 , xa2 , x−1 a2 }.
Each of these possibilities contradicts one of the properties of being a suitable pair: any of
the first four would contradict (ii); either of the last two contradict (iii).
7

If on the other hand the second possibility holds, then ϕ(xa2 ) = xa−1
2 a1 ∈ NxA (1).
Again, each possible equality contradicts one of the properties of being a suitable pair:
either of the first two contradict (i); the third or fourth each contradicts (ii); and either of
the last two contradict (iii). We therefore conclude that ϕ(x) ∈ {x, x−1 }, as claimed.
Next we show that ϕ(a) = a for every a ∈ A.
Observe that
NA (x−1 ) = NA (x) = {1, y, a1, ya1 , a2 , ya2}.
Thus, since ϕ(x) ∈ {x, x−1 }, we have ϕ(NA (x)) = NA (x). If ϕ(a) = a−1 for every a ∈ A,
then this implies that a−1
1 ∈ NA (x), leading to a contradiction to the definition of a suitable
−1
pair, as above. (If a1 is any of the first four elements, this contradicts (ii); if it is either
of the last two, this contradicts (iv).) Thus, we must have ϕ(a) = a for every a ∈ A.
Next we show that if ϕ(x) = x then ϕ = 1.
Since the induced subgraph on xA is isomorphic to ∆ and has Cayley index 2, we must
either have ϕ(xa) = xa−1 for every a ∈ A, or ϕ(xa) = xa for every a ∈ A. In the latter
case, ϕ = 1 and we are done. In the former case, we must have ϕ(NA (xa−1
1 )) = NA (xa1 ).
−1 −1
−1
Observe that a1 = xa1 x ∈ NA (xa1 ), so this would imply that
−1
−1
−1
a1 = ϕ(a1 ) ∈ NA (xa1 ) = {a−1
1 , ya1 , 1, y, a1 a2 , ya1 a2 }.

Similar to the arguments above, each of these possibilities contradicts some property of
suitable pairs. If a1 were any of the first four elements of NA (xa1 ) this would contradict
(i); if it were either of the last two, this would contradict (iii).
Finally, we show that if ϕ(x) = x−1 then ϕ(xa) = (xa)−1 for every a ∈ A.
Again since the induced subgraph on xA is isomorphic to ∆ and has Cayley index 2, we
must either have ϕ(xa) = (xa)−1 for every a ∈ A, or ϕ(xa) = x−1 a−1 for every a ∈ A. In
the former case we are done. In the latter case, we must have ϕ(NA (x−1 a−1
1 )) = NA (xa1 ).
−1 −1
Observe that a1 = x−1 a−1
x
∈
N
(x
a
),
so
this
would
imply
that
a
=
ϕ(a
A
1
1 ) ∈ NA (xa1 ),
1
1
yielding the same contradiction as in the previous paragraph.

Proposition 5.5. Let A1 = hz1 i be a cyclic group of order 2n ≥ 6, and A2 = hz1 , z2 i
with |z2 | = 2 and z1 z2 = z2 z1 . Let S1 = {z1 , z1−1 } and S2 = {z1 , z1−1 , z2 }, and let D1 =
Dic(A1 , z1n , x), and D2 = Dic(A2 , z2 , x). Then
Γi = Cay(Di , Si ∪ {x, x−1 , xz1 , xz1n+1 , xz1−2 , xz1n−2 })
for i ∈ {1, 2} is connected and has Cayley index 2 when n ≥ 5, and Γ2 is connected and
has Cayley index 2 when n ≥ 3.
Proof. It is easy to see that S1 is the connection set for a Cayley graph on A1 with Cayley
index 2. It is slightly less obvious that S2 is the connection set for a Cayley graph on
A2 with Cayley index 2, but becomes clear upon noting that each a-edge lies in a unique
4-cycle, while each b-edge lies in two 4-cycles. Fix i ∈ {1, 2}, and if i = 1, ensure that
n ≥ 5.
By Lemma 5.2 or Lemma 5.3, we know that (z1 , z1−2 ) is a suitable pair for Di , and that
for any ϕ ∈ Aut(Γi )1 , ϕ(Ai ) = Ai . By Lemma 5.4 with S = Si and this suitable pair, we
8

see that there are only two possibilities for ϕ: ϕ = 1, or ϕ(a) = a and ϕ(xa) = (xa)−1 for
every a ∈ A. Thus, Γ has Cayley index 2.

Proposition 5.6. Let A be an abelian group of even order that contains an involution y,
and let D = Dic(A, y, x). Suppose that D has a connected MRR with Cayley index 2. Let
A′ = A × Z2 . Then D ′ = Dic(A′ , y, x) has Cayley index 2.
Proof. Observe that D ′ ∼
= D × Z2 . The result is now immediate from Corollary 4.4.



As an immediate consequence of Proposition 5.5 and Proposition 5.6, we obtain the
following.
Corollary 5.7. The following generalised dicyclic groups have Cayley index 2:
• Dic(A × Zk2 , z1n , x) where A = hz1 i ∼
= Z2n , n ≥ 5, and k ≥ 0; and
• Dic(A × Zk2 , z2 , x) where A = hz1 , z2 i ∼
= Z2n × Z2 , |z1 | = 2n, |z2 | = 2, n ≥ 3, and
k ≥ 0.
We note that if n is odd, then Z2n × Z2 has only one automorphism class of elements of
order 2, so that Corollary 5.7 provides two MRRs for all such groups when n ≥ 5.
We can determine the generalised dicyclic groups that remain by considering all abelian
groups of even order at most 48. For each group, we choose one representative for each automorphism class of elements of order 2 to be the distinguished element y = x2 . By Corollary 5.7, we can ignore the cyclic groups of order at least 10, and all but two small groups
that have the form Z2n × Z2 . We also eliminate any groups that are abelian or that have
the form Q8 × Zn2 . Finally, if a group has the form D × Z2 for some smaller generalised
dicyclic group D with c(D) = 2, then Corollary 4.4 gives c(D × Z2 ) = 2, so we do not have
to consider these groups either.
We conclude this section and the paper with Table 4, showing the Cayley index and
the connection set for an MRR for each of the 15 generalised dicyclic groups that are not
already covered by any of the preceding results. For three of these groups that have the
form D × Z2 for some smaller generalised dicyclic group D, we use Corollary 4.4, but only
after showing that c(D) = 2. For these, instead of explicitly giving the connection set for
an MRR, we present the group as D × Z2 .
As in Section 3, if A is an abelian group that we are presenting as being isomorphic to
Zi1 × . . . × Zik , then we let {z1 , . . . , zk } be the canonical generating set for this group, so
|zj | = ij .
References
[1] D. Byrne, M. Donner and T. Sibley, Groups of graphs of groups, Beitr. Algebra Geom. 54 (2013),
323–332.
[2] The GAP Group, GAP – Groups, Algorithms, and Programming, Version 4.8.6 ; 2016,
http://www.gap-system.org.
[3] C. D. Godsil, GRRs for nonsolvable groups, Algebraic Methods in Graph Theory, (Szeged, 1978),
221–239, Colloq. Math. Soc. János Bolyai 25, North-Holland, Amsterdam-New York, 1981.
[4] D. Hetzel, Über reguläre graphische Darstellung von auflösbaren Gruppen, Technische Universität,
Berlin, 1976.
9

Group
Cayley index
Connection set for an MRR
Dic(Z6 , 3, x)
4
{z1±1 , x±1 }
Dic(Z8 , 4, x)
4
{z1±1 , x±1 }
Dic(Z4 × Z2 , (0, 1), x)
4
{z1±1 , x±1 , (z1 x)±1 }
±1
Dic(Z8 × Z2 , (4, 0), x)
2
{z1 , z2 , x±1 , (z1 x)±1 , (z2 x)±1 }
Dic(Z4 × Z4 , (2, 0), x)
2
{z1±1 , z2±1 , (z1 z2 )±1 , x±1 , (z1 x)±1 }
Dic(Z4 × Z22 , (0, 1, 0), x)
2
{z1±1 , z3 , x±1 , (z1 x)±1 , (z3 x)±1 }
Dic(Z6 × Z3 , (3, 0), x)
2
{z1±1 , z2±1 , x±1 , (z2 x)±1 , (z1 z2 x)±1 }
Dic(Z8 × Z4 , (4, 0), x)
2
{z1±1 , z2±1 , x±1 , (z16 z2−1 x)±1 , (z15 z2 x)±1 }
Dic(Z8 × Z4 , (0, 2), x)
2
{z1±1 , z2±1 , x±1 , (z15 x)±1 , (z13 z2 x)±1 }
Dic(Z24 × Z2 , (2, 0, 0), x)
2
D∼
= Dic(Z4 × Z4 , (2, 0), x) × Z2
Dic(Z4 × Z4 × Z2 , (0, 0, 1), x)
2
{z1±1 , z2±1 , x±1 , (z23 x)±1 , (z13 z22 x)±1 }
Dic(Z4 × Z32 , (0, 1, 0, 0), x)
2
D∼
= Dic(Z4 × Z22 , (0, 1, 0), x) × Z2
±1 ±1
Dic(Z12 × Z3 , (6, 0), x)
2
{z1 , z2 , x±1 , (z17 z2 x)±1 , (z13 z2 x)±1 }
Dic(Z6 × Z6 , (3, 0), x)
2
D∼
= Dic(Z6 × Z3 , (3, 0), x) × Z2
±1 ±1
Dic(Z12 × Z4 , (6, 0), x)
2
{z1 , z2 , x±1 , (z14 z2 x)±1 , (z19 z23 x)±1 }
Table 4. MRRs for generalised dicyclic groups

[5] W. Imrich, Graphen mit transitiver Automorphismengruppen, Monatsh. Math. 73 (1969), 341–347.
[6] W. Imrich, Graphs with transitive abelian automorphism group, Combinat. Theory (Proc. Colloq.,
Balatonfűred, 1969), Budapest, 1970, 651–656.
[7] W. Imrich, On graphs with regular groups, J. Combinatorial Theory Ser. B 19 (1975), 174–180.
[8] W. Imrich and M. E. Watkins, On automorphism groups of Cayley graphs, Period. Math. Hungar. 7
(1976), 243–258.
[9] L. Nowitz and M. E. Watkins, Graphical Regular Representations of non-abelian groups I, Canadian
J. Math. 24 (1972), 993–1008.
[10] L. Nowitz and M. E. Watkins, Graphical Regular Representations of non-abelian groups II, Canadian
J. Math. 24 (1972), 1009–1018.
[11] SageMath, the Sage Mathematics Software System (Version 7.5.1), The Sage Developers, 2017,
http://www.sagemath.org.
[12] M. E. Watkins, On the action of non-abelian groups on graphs, J. Combin. Theory 11 (1971), 95–104.
[13] M. E. Watkins, On Graphical Regular Representations of Cn × Q, Graph theory and its applications,
Lecture Notes in Mathematics 303, Springer, Berlin 1972, 305–311.
[14] M. E. Watkins, Graphical Regular Representations of alternating, symmetric, and miscellaneous small
groups, Aequat. Math. 11 (1974), 40–50.
Department of Mathematics and Computer Science, University of Lethbridge, Lethbridge, AB T1K 3M4, Canada
E-mail address: joy.morris@uleth.ca
E-mail address: josh.tymburski@uleth.ca

10

