5 - Strongly regular graphs

Summary

A graph on v vertices is a strongly regular graph with parameters (v, k; a, c) if:

1. (a) it is k-regular;

2. (b) each pair of adjacent vertices in the graph have exactly a common neighbors;

3. (c) each pair of distinct nonadjacent vertices in the graph have exactly c common neighbors.

If X is a strongly regular graph, then its complement is also a strongly regular graph. A strongly regular graph X is primitive if both X and its complement are connected. If X is not primitive, we call it imprimitive. The imprimitive strongly regular graphs are exactly the disjoint unions of complete graphs and their complements, the complete multipartite graph. It is not difficult to show that a strongly regular graph is primitive if and only if 0 < c < k. It is customary to declare that the complete and empty graphs are not strongly regular, and we follow this custom.

Two examples of strongly regular graphs are the line graphs of complete graphs and the line graphs of complete bipartite graphs. We will meet other large classes of examples as we go through this chapter – most of which arise from well-known combinatorial objects. In this chapter we provide detailed information about the cliques and cocliques for many of these graphs. We see that many interesting objects from design theory and finite geometry occur encoded as cliques and cocliques in these graphs, and this leads to interesting variants of the EKR Theorem.

An association scheme

As stated in the previous chapter, association schemes with two classes are equivalent to strongly regular graphs. Throughout this section we denote the adjacency matrix of a graph X by A, rather than A (X), and the adjacency matrix of the complement of X by Ā, rather than.

Lemma. Let X be a graph. Then X is strongly regular if and only if A = { I,A,Ā} is an association scheme.

Proof. Assume that X is a strongly regular graph with parameters (v, k; a, c). It is clear that the set of matrices A = { I,A, Ā} satisfies properties (a) through (c) in the definition of an association scheme given in Section 3.1.We only need to confirm that the product of any two matrices in A is a linear combination of other matrices in A (in doing this, we also show that the matrices commute).