Strongly regular Cayley graphs, their representations and eigenvalues

Eigenvalues and characters of Cayley graphs

     When we looked at strongly regular graphs, we noted the powerful results that could be obtained from the eigenvalues of the adjacency matrix.  We found, for example, that the two (16, 6, 2, 2) graphs had eigenvalues 6, 2 and –2, with multiplicities 1, 6 and 9.  In general, strongly regular graphs have just three eigenvalues:  the eigenvalue k equal to the degree of the graph and two other eigenvalues which are roots of the quadratic polynomial

x^2 -(lambda - mu)x - (k-mu).

If the graph is a Cayley graph, with S the neighborhood of the identity,

  

then we may view the graph as existing within the group, in some sense, and we may then use the representations of the group to gain information about this structure.  In particular, if the group is abelian, the characters of the group, when applied to the set S, give the eigenvalues of the graph!

Here are the character values of the abelian group C4 x C4 applied to the generating set S =(x+x^2+x^3)+(y+y^2+y^3).  Notice how in six places the character sends S to 2.  In 9 places, the character values are –2 and in one case (always the trivial representation), the set S is sent to the degree, 6.

A similar picture appears when we look at the Shrikhande graph.  Again the character values give us the eigenvalues! (Here S =(x+x^3)+(xy+x^3y^3)+(y+y^3).)

The fact that character values (on S) are the eigenvalues of the graph is a powerful result.  It comes from the fact that the regular representation of the group decomposes into irreducible representations and the regular representation applied to S is an adjacency matrix of the graph.  The diagonalization of the adjacency matrix parallels to decomposition of the regular representation.

The effect of this result is that we can draw the eigenvalue techniques into the group setting and combine the linear algebra tools with group representation techniques.

The dual Cayley graph

     The characters of an abelian group form a group themselves, under the pointwise product of the functions (fg(x):=f(x)g(x)).  This group, G*, is isomorphic to the original group, G.  Thus we make take a Cayley graph Cay(G,S), fix an eigenvalue theta and create a set S* of the characters which map S to theta.  The dual group G* and the set S* of certain characters gives a Cayley graph Cay(G*,S*).  If the original graph Cay(G,S) is a strongly regular graph then the graph Cay(G*,S*) is also strongly regular.  However, the new graph need not have the same parameters as the original.

However, in all the cases of which I am aware, the dual Cayley graph has the same parameters and is isomorphic to the original.  I think this just shows how few of these I know....  I hope to know more this summer after the NSF-REU at Sam Houston.

More on this later!

Next time: Undergraduate Research Centers in Texas

[Mathematical prerequisites: This article requires an introduction to finite graphs, an elementary introduction to some concepts in matrix theory, and some basic understaninding of group theory]

Follow Ken W. Smith on Twitter @kenwsmith54

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