Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 3 (2010) 147–150
A note on quotients of strongly regular graphs
Michael Giudici ∗, Murray R. Smith
School of Mathematics and Statistics, The University of Western Australia
35 Stirling Highway, WA 6009, Australia
Received 9 March 2010, accepted 9 September 2010, published online 21 October 2010
Abstract
We give examples of vertex-transitive strongly regular graphs with a normal quotient
which is neither complete nor strongly regular.
Keywords: Strongly regular graph.
Math. Subj. Class.: 05E30
1 Results
A strongly regular graph is a graph that is not complete and for which each vertex has
valency k and there exist integers λ, µ such that each pair of adjacent vertices have λ
common neighbours and each pair of non-adjacent vertices have µ common neighbours.
Such a graph is usually denoted by srg(v, k, λ, µ) where v is the number of vertices.
One common method for studying graphs is by taking quotients. Given a partition B
of the vertex set of a graph Γ, the quotient graph is the graph whose vertices are the parts
of the partition B and two parts B1 and B2 are joined by an edge if there exist v ∈ B1 and
w ∈ B2 such that v is adjacent to w in the original graph Γ. When B is the set of orbits of a
normal subgroupN of some groupG of automorphisms of Γ we denote the quotient by ΓN
and refer to it as a normal quotient. It was shown in [5] that if Γ is a strongly regular graph
with a group of automorphismsGwhich acts transitively on the vertex set and edge set of Γ
then for a nontrivial normal subgroup N of G, the normal quotient ΓN is either a complete
graph or a strongly regular graph. The purpose of this note is to show that edge-transitivity
is indeed required.
In Example 1.1, we provide a vertex-transitive, edge-intransitive strongly regular graph
Γ where we take G to be the full automorphism group and obtain a normal quotient which
is neither strongly regular nor complete. The graph Γ also has the following interesting
properties:
∗The first author is supported by an Australian Research Fellowship.
E-mail addresses: giudici@maths.uwa.edu.au (Michael Giudici), murray@murraysmith.id.au (Murray R.
Smith)
Copyright c© 2010 DMFA Slovenije
148 Ars Math. Contemp. 3 (2010) 147–150

0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0
1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1
1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0
1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 1
1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0
1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0
1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1
1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1
1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1
1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1
1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0
1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 0
1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0
0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1
0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0
0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1
0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0
0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0
0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1
0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1
0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0
0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0
0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 0
0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1
0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1
0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1
0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0
0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1
0, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0
0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0
0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0
0, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0
0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 0
0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0

Figure 1: The matrix A.
1. Γ is a Cayley graph for three different isomorphism types of groups.
2. Aut(Γ) contains five conjugacy classes of regular subgroups, of which 4 are normal
subgroups.
3. Aut(Γ) contains two isomorphic regular subgroups of shape C23 oC22 for which one
is normal in Aut(Γ) while the other is not, that is, Γ is both a normal Cayley graph
and a nonnormal Cayley graph for isomorphic groups.
Other examples of Cayley graphs that are both normal and nonnormal Cayley graphs
for isomorphic groups are given in [1, 6].
In Example 1.2 we provide an infinite family of strongly regular graphs where we take
G to be a vertex-transitive proper subgroup of the full automorphism group and obtain
normal quotients which are neither strongly regular nor complete.
Example 1.1. Let Γ be the strongly regular graph with adjacency matrix A given in Fig-
ure 1 which has parameters srg(36, 14, 4, 6). The adjacency matrix was retrieved from [7].
M. Giudici and M. R. Smith: A note on quotients of strongly regular graphs 149

0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0
1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0
1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0
1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1
1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1
1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1
1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0
1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1
1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1
1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1
1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1
1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1
0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1
0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1
0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1
0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0
0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0
0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0

Figure 2: The matrix B.
According to a GAP [3] calculation, Aut(Γ) equals
〈 (2, 15)(3, 7)(4, 9)(5, 12)(6, 14)(8, 11)(10, 13)(16, 23)(17, 32)(18, 27)(19, 21)(20, 26)(22, 25)
(31, 35)(34, 36),
(3, 5)(4, 6)(7, 12)(8, 11)(9, 14)(10, 13)(16, 21)(17, 20)(18, 22)(19, 23)(25, 27)(26, 32)(28, 29)
(30, 33)(31, 34)(35, 36),
(1, 25, 32, 2, 26, 27)(3, 15, 5, 4, 24, 6)(7, 21, 33, 18, 13, 31)(8, 14, 28, 19, 20, 36)(9, 11, 35, 17, 23, 29)
(10, 22, 30, 16, 12, 34)
〉
which has shape C26 o C22 . (By a group G of shape H oK we mean that G has a normal
subgroupH and a subgroupK such thatH∩K = 1. Since this does not specify howK acts
on H there may be more than one isomorphism class of groups of a given shape.) In fact,
G ∼= Z26 o 〈σ, τ〉 acting on Z26, with Z26 acting regularly on itself and (a, b)τ = (−a,−b)
and (a, b)σ = (b, a). Thus Aut(Γ) is vertex-transitive and is a Cayley graph for H1 = Z26.
The joining set is
{(0, 5), (0, 1), (0, 3), (5, 0), (1, 0), (3, 0), (1, 3), (5, 3), (3, 1), (3, 5),
(1, 5), (5, 1), (2, 4), (4, 2)}.
Since Aut(Γ)(0,0) = 〈τ, σ〉 has five orbits on this set, Aut(Γ) has five orbits on edges.
Now Aut(Γ) has a normal subgroup N of order two generated by the element (3, 3) ∈
Z26 and which is the centre of Aut(Γ). The group N has 18 orbits of length two on the 36
vertices of Γ and the set of neighbours of (0, 0) contains the three N -orbits {(0, 3), (3, 0)},
{(1, 5), (5, 1)} and {(2, 4), (4, 2)}. Hence, ΓN is a valency 11 graph on 18 vertices of
diameter 2 but is not strongly regular. Indeed there are no feasible parameters for strongly
regular graphs on 18 vertices which are not complete multipartite [4, p227]. The matrix B
given in Figure 2 is the adjacency matrix for ΓN .
Not only is Γ a Cayley graph for H1, which is normal in Aut(Γ), we also have that
H2 = 〈(2, 0), (0, 2), (3, 0)τ, (0, 3)τ〉, H3 = 〈(0, 2), (2, 0), (3, 0)σ〉 and H4 = 〈(2, 0),
(0, 2), (2, 5)στ〉 are normal subgroups of Aut(Γ) that act regularly on V Γ. The sub-
group H2 has shape C23 o C22 , while H3 ∼= H4 have shape C23 o C4. Finally, H5 =
〈(2, 0), (0, 2), (1, 0)τ, (0, 1)〉 ∼= H2 is a regular subgroup of Aut(Γ) which is not normal.
Thus Γ is a Cayley graph for three different isomorphism types of groups. A Magma [2]
150 Ars Math. Contemp. 3 (2010) 147–150
calculation shows that H1, H2, H3, H4 and the subgroups conjugate to H5 are the only
regular subgroups of Aut(Γ).
The automorphism group of ΓN is isomorphic to S2×S4×S3, which is vertex-transitive
and has three orbits on edges. Note that Aut(Γ)/N < Aut(ΓN ). The automorphism group
contains 4 conjugacy classes of regular subgroups, none of which are normal in Aut(ΓN ).
One class is isomorphic to C23 × C2, and there are three classes of subgroups with shape
C23 o C2, with two of the classes being isomorphic to each other. Representatives of these
four conjugacy classes are Hi/N for i = 1, 2, 3, 4. Note that H2/N = H5N/N .
Example 1.2. Let Γ = H(2,m), the Hamming graph withm2 vertices and suppose thatm
is not a prime. Then Γ is a strongly regular graph with parameters (m2, 2(m−1),m−2, 2).
Let G = M1 ×M2, with M1 ∼= M2 ∼= Cm, act regularly on the set of vertices of Γ. Let
N1 6 M1 and N2 6 M2 and N = N1 × N2 C G. Consider the graph ΓN . Then ΓN
is the cartesian product of Kr and Kk where |M1 : N1| = r and |M2 : N2| = k. The
adjacent vertices (a, b1), (a, b2) in ΓN have k−2 common neighbours, namely the vertices
of the form (a, b) with b 6= b1, b2. However, the adjacent vertices (a1, b), (a2, b) have r− 2
common neighbours, these being the vertices of the form (a, b) with a 6= a1, a2. Hence for
r 6= k, the graph ΓN is not strongly regular.
2 Acknowledgements
The authors are grateful to the anonymous referees whose comments greatly improved the
paper and led to Example 1.2.
References
[1] J. Bamberg and M. Giudici, Point regular automorphism groups of generalised quadrangles,
submitted, arXiv:1005.2250v1.
[2] W. Bosma, J. Cannon and C. Playoust, The Magma algebra system, I. The user language. J.
Symbolic Comput. 24 (1997) 235–265.
[3] The GAP Group, GAP–Groups, Algorithms, and Programming, Version 4.3, 2002, http:
//www.gap-system.org.
[4] C. Godsil and G. F. Royle, Algebraic Graph Theory, Graduate Texts in Mathematics, 207,
Springer-Verlag, New York, 2001.
[5] J. Morris, C. E. Praeger and P. Spiga, Strongly regular edge-transitive graphs, Ars Math. Con-
temp. 2 (2009), 137–155.
[6] 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.
[7] E. Spence, http://www.maths.gla.ac.uk/˜es/srgraphs.html.