Strongly regular Cayley graphs: Introduction

Strongly regular Cayley graphs

Many strongly regular graphs possess high symmetry.  No vertex is different than any other; one may transform vertices in a one-to-one fashion so that the resulting graph is unchanged.   In mathematical terminology, these graphs have automorphisms which act transitively on the vertex set.

The (9,4,1,2) graph is an example of this

 as is the Petersen graph.

The collection of symmetries (automorphisms) of a graph form a group under function composition.  In many cases we may take advantage of this group of symmetries and visualize the vertex set itself as the set of elements of a group.  We do this by picking a "base" vertex to label as the identity element (it does not matter which vertex we choose) and then we label each other vertex in the graph by the group element g which maps the base vertex to the other vertex.

Sometimes this works; sometimes it doesn't.  For example, we can label the vertices of the (9,4,1,2) graph, above, by the elements of the group Z3 x Z3 = {(00),(01),(02), (10),(11),(12), (20),(21),(22)}.  We might choose the red vertex at the top left as the identity, (00), and then agree that its neighbors at the top (green, then blue) be assigned group elements (10), (20), respectively.  The next row (blue, red, green, in that order) are assigned (01), (11), and (21) and the final set at the bottom are (02), (12), (22).  With this assignment, we can think of the vertex (ab) as telling us "move over a and then move down b" in the 3 x 3 square of vertices.

When we can make this construction work, we have a Cayley graph Cay(G,S).  The group G is the group of labels for the vertices and the set S is the neighborhood of the identity element.  The (9,4,1,2) graph is Cay(G,S) where G = Z3 x Z3 and S = {(10),(20),(01),(02)}.

We cannot do this with the Petersen graph.  Although the Petersen graph has many symmetries – there are 120 automorphisms of Petey; they form, Sym(5), the symmetric group on 5 letters – it is not possible to view the Petersen graph as a Cayley graph.  This is because there is no group of order 10 which acts transitively on the vertices of that graph (moving a fixed vertex to any other.)  The cyclic group of order 10 does not act as an automorphism group of the Petersen graph and the dihedral group of order 10, although acting as an automorphism group, is not transitive.  Since there are only two groups of order 10, the cyclic and the dihedral, then we have exhausted our options for a Cayley group in this case.

The Petersen graph is an interesting example; although it cannot be described as a Cayley graph, it can be constructed from 10 cosets of a subgroup of Sym(5).  That subtlety is worth exploring at some point....

A significant research question at this stage is, Which strongly regular graphs are Cayley graphs?  Even if we know a strongly regular graph exists, we are still interested in the question, Does the graph have an automorphism group of size v acting transitively on the points?


A strongly regular Cayley graph is also called a partial difference set (PDS). The terms are almost equivalent; a partial difference set might have the identity 1 in S, in which case our graph has loops.  We forbid loops in our Cayley graphs so a PDS is a (small) generalization of SR Cayley graphs.

The two (16,6,2,2) graphs

In the first blog on strongly regular graphs, we described an SRG with parameters (16,6,2,2), the Shrikhande graph.  There are, in fact, two different (nonisomorphic) SRGs with parameters (16,6,2,2).  Both are Cayley graphs in the group Z4 x Z4. One is the Shrikhande graph; the other is the "rook" graph.  The "rook" graph on n^2 points is obtained by arranging the points in an n x n grid and then assigning adjacency to pairs of vertices that are in the same row or same column.  Thus the reason for the term "rook":  adjacency describes rook moves on the n x n chess board.

The rook graph on the 4x4 board is given below.  In this drawing, each vertex is represented as an element of the group Z4 x Z4.

We may view this graph as a Cayley graph by noting that the neighborhood of the identity (00) is the set of six vertices S={(10),(20),(30),(01),(02),(03)}.

We may represent this group G and set S using multiplicative notation, so that G = C4 x C4 and S = x+x^2+x^3+y+y^2+y^3.  Note that we now treat S as a formal sum, instead of a list.  

In the rook graph, the neighborhood of the identity, 1, has two triangles, drawn in red, below.

On the other hand, the Shrikhande graph is also a Cayley graph.  But here S is different; in multiplicative notation, S is the sum x+x^3+y+y^3+xy+x^3y^3.  When viewed as the neighborhood of the identity, we see, instead of two triangles, a single 6-cycle, (x,xy,y,x^3,x^3y^3,y^3.)  

The difference in the neighborhoods make it clear that these graphs (the rook graph and Shrikhande graph) are truly different; they are nonisomorphic SRGs, even though they have the same parameters.

There are lots of open questions about Strongly regular Cayley graphs.  Many of these are accessible to undergraduates with a course in group theory.  Indeed, this subject will be one of the research topics in the NSF-REU at Sam Houston that I will be directing in June.  Of course, for this reason, there is a lot more I want to say about these interesting objects!  I'll see if I get the time....

Next time: Strongly Regular Cayley Graphs: their representations and eigenvalues

[Mathematical prerequisites: This article requires an introduction to finite graphas and an elementary introduction to some concepts in matrix theory.]

Follow Ken W. Smith on Twitter @kenwsmith54