The Shrikhande graph

In 1993, Derek Holton and John Sheehan published a book on the Petersen graph. This object is probably the most famous finite graph, and is an example or counterexample to many conjectures. (It was originally introduced by Petersen to debunk a proposed proof of the Four-Colour Conjecture by Tait, who had shown the equivalence of the conjecture to the statement that any planar bridgeless cubic graph has a 1-factorization, and hoped to prove that every bridgeless cubic graph has a 1-factorization; the Petersen graph has a 1-factor but no 1-factorization.

It is said that any new conjecture in graph theory should be tested first on the Petersen graph. Probably having the book by Holton and Sheehan on your desk is necessary for this!

A few years ago, Ambat Vijayakumar persuaded me that we should do something similar with the Shrikhande graph (which I will describe shortly). I think he had in mind a book something like Holton and Sheehan had produced. But as we thought about it, we realised that our net would have to be cast more widely; there are many areas of discrete mathematics in which this graph plays an important role.

The book has just been accepted for publication by Cambridge University Press, though I am tempting fate a bit, since we haven’t actually signed contracts yet. The authors are Vijay, his colleage Aparna Lakshmaanan S, and me.

It begins with a biographical account of Shrikhande, and an introduction to graph theory, containing all the definitions we were likely to need (and possibly some others too). The rest of the book is a description of six different constructions of the Shrikhande graph, together with a textbook account of the relevant area of discrete mathematics. I will now describe the context in which Shrikhande discovered his graph, and discuss our six constructions in turn.

One definition before we begin. A graph is strongly regular, with parameters (n,k,λ,μ) if

• it has n vertices;
• it is regular, with degree k;
• two distinct vertices have exactly λ common neighbours if they are adjacent, and μ if they are nonadjacent.

The spectrum of a strongly regular graph (the eigenvalues of the adjacency matrix and their multiplicities) can be computed from these parameters.

First construction: bare hands

The Shrikhande graph is a graph with 16 vertices; it is regular with degree 6, and any two points have two common neighbours. So it is strongly regular, with parameters (16,6,2,2). It shares these properties with the line graph of the complete bipartite graph on 4+4 vertices (aka the 4×4 square lattice graph L₂(4): the vertices form a 4×4 array, and vertices in the same row or column of the array are joined.)

From this, it follows that the SG (as I will call it for short) and L₂(4) have the same spectrum (the eigenvalues are 6, 2 and −2, with multiplicities 1, 6, 9 respectively.)

Shrikhande’s theorem states the following:

Let G be a graph which is strongly regular with the same parameters as the n×n square lattice graph (equivalently, has the same spectrum as this graph L₂(n)). Then:

• If n ≠ 4, then G is isomorphic to L₂(n).
• If n = 4, then G is isomorphic to either L₂(4) or SG.

The graph SG was constructed for the first time in his paper.

Here is a very brief outline of the proof. This is more or less the same as Shrikhande’s proof. Consider an unknown graph with the same parameters as the square lattice but not isomorphic to it. First, show that the neighbourhood of any vertex in the graph (which has 6 vertices and degree 2) is a 6-cycle. Then there are 9 further vertices; show that each is joioned to two vertices in the 6-cycle, these two forming either an edge (6 possibilities) or a long diagonal (3 possibilities). Then a little further argument sorts out the adjacencies among the 9 vertices; there is a unique possibility for these.

From these we deduce several things. First, the uniqueness of the graph. Second, the fact that the group of automorphisms fixing a vertex is the group of the 6-cycle (the dihedral group of order 12). Third, since the construction is the same from any vertex, the full automorphism group of SG is transitive on vertices, and so has order 16×12 = 192. And fourth, we have an algorithm for recognising that a graph we meet later is isomorphic to SG: select a vertex; check that its six neighbours carry a cycle; and check that the remaining 9 vertices have the correct adjacencies to the cycle and to one another.

Furthermore, since a vertex neighbourhood contains edges but no triangles, the clique number of SG is 3.

Second construction: as a Cayley graph

SG is a Cayley graph for the group C₄×C₄, which I will write additively. If the two factors are generated by a and b, we take the elements of the group as the vertices, and join two vertices if their difference is ±a, ±b, or ±(a−b).

This simple construction allows the graph to be built with a few lines of code in a computer algebra system. It also gives further information. For example, the chromatic number of SG is 4. For the subgroup generated by 2a and 2b contains no edges; so its four cosets give a proper colouring of the graph.

Third construction: as a Latin square graph

A Latin square is a square array of size n whose entries are taken from an alphabet of size n such that each letter occurs once in each row and once in each column. Two Latin squares of the same size (using different alphabets) are orthogonal if, when they are superimposed, each pair consisting of one letter from each alphabet occurs exactly once. Euler called this a Graeco-Latin square, since he used the Latin and Greek alphabets; the term “Latin square” is a back-formation from this.

Euler was able to construct a Graeco-Latin square for every size n not conjugate to 2 modulo 4. It is easy to see that there is no square of order 2. Euler tried but failed to make a construction in the next case, n = 6, and conjectured that Graeco-Latin squares would not exist for any order congruent to 2 mod 4.

This conjecture stood for nearly two centuries until it was refuted as strongly as possible by Bose, Shrikhande and Parker (the “Euler spoilers”) in 1959; they showed that these squares do exist for all orders n with the exception of 2 and 6. This, in Shrikhande’s estimation, was the achievement of which he was most proud.

Returning to Latin squares, we can construct a strongly regular graph from a Latin square of order n as follows: the vertices are the cells of the square; two vertices are joined if they lie in the same row or same column or contain the same entry. These graphs are strongly regular (indeed, Latin squares form one of the most prolific sources of such graphs), and they determine the squares up to the notion of “paratopism” (which allows permuting rows, columns and letters as well as permuting the roles of these three types of object).

Now there are just two different Latin squares of order 4, the Cayley tables of the two groups of order 4 (namely C₄ and C₂×C₂. The complements of these graphs are respectively SG and L₂(4).

Fourth construction: on a torus

The Shrikhande graph is not planar, but it can be drawn on the torus: take the regular tesselation of the plane by triangles, and fold it up to form a torus so that four steps in any direction bring you back to your start.

It forms a regular map: this means that the group of map automorphisms acts (sharply) transitively on vertex-edge-face flags. Since there are 16 vertices, 6 edges through each vertex, and two faces on each edge, the group of map automorphisms has order 192; it is the same as the group of graph automorphisms.

On the sphere, if you draw an icosahedron, and form its dual by putting a new vertex in the centre of each face and joining two new vertices if the faces form an edge, you obtain the dodecahedron. In the same way, we can take the dual of the SG on the torus. The resulting graph, with 32 vertices, degree 3, and hexagonal faces, turns out to be the Dyck graph, which is considerably older than the Shrikhande graph.

Fifth construction: in an exceptional root system

Shrikande’s discovery of his graph had a couple of contexts at the time. One was the notion of an association scheme, which had been introduced by his doctoral supervisor R. C. Bose for use in statistics. Statisticians have need to perform calculations on matrices whose size is the number of experimental units; before computers or even desk calculators, this was a difficult job, but could be made simpler if the matrix had a pattern, and association schemens were designed to provide such a pattern.

The other context was a programme led by Alan Hoffman, to find all graphs with smallest eigenvalue −2. Hoffman himself proved a theorem like Shrikhande’s for the triangular graphs, the line graphs of complete graphs, with the exception of n = 8; this value was later settled by Chang Li-Chien, who showed that there are three exceptional graphs.

Hoffman made a remarkable conjecture, which I give here in slightly stronger form: a connected graph with smallest eigenvalue −2 or greater is either a generalized line graph or one of finitely many exceptional graphs. His actual conjecture was a little weaker, only asking that such graphs with sufficiently large degree should be generalized line graphs. These are a class of graphs devised by Hoffman, which all do have smallest eigenvalue −2 or greater. Hoffman came close to a proof of his conjecture, and later proved a still stronger result. But the strong form I have stated above was proved by Jean-Marie Goethals, Jaap Seidel, Ernie Shult and me, using the theory of root systems with all roots of the same length. I have told the story of this in my series of posts about the ADE affair. The finitely many exceptions are all represented in the three exceptional root systems E₆, E₇, E₈.

The proof shows that the Shrikhande graph can be represented as a set of 16 roots in the root system E₇, any two making an angle of 90 or 60 degrees; two vertices are joined if the roots are at 60 degrees. We give an explicit construction of SG in E₇ in the book.

Sixth construction: Seidel switching

This is an important operation, connected with other topics in discrete mathematics such as sets of equiangular lines in Euclidean space and double covers of complete graphs.

The operation of switching a graph with respect to a set A of vertices involves changing edges between A and its complement into non-edges, and non-edges into edges, but leaving edges and non-edges within or outside A alone.

A precursor to the proof of Hoffman’s conjecture was the classification by Seidell in the late 1960s of the strongly regular graphs with smallest eigenvalue −2. In the course of this, Seidel showed that SG can be obtained from L₂(4) by switching. We give this explicitly in the book; the switching set in L₂(4) can be chosen to be a diagonal of the square grid (or indeed, any common transversal to rows and columns).

The book

The book is now written and accepted for publication; we await contracts. We have tried to aim it at students, and hope that a number of different courses could be designed starting with the Shrikhande graph and folloiwing one or more of the directions we outline.