Up

Strongly regular graphs

A graph is a collection of points, where certain pairs of points are joined by an edge. It is a graphical representation of a symmetric relation. There are lots of them. A strongly regular graph is a very beautiful graph, and there are not very many strongly regular graphs on a given number of points. The definition is as follows.

A strongly regular graph with parameters (v,k,λ,μ) is a graph with v points (vertices), such that each point has precisely k neighbours (i.e., is joined by an edge to precisely k other vertices), where the number of common neighbours of two vertices equals λ in case they were neighbours, and equals μ in case they weren't.

In order to have well-defined λ and μ, we require that there is at least one pair of neighbours (that is, k is not zero), and at least one pair of non-neighbours (that is, k is less than v−1).

The complement of a strongly regular graph with parameters (v, k, λ, μ) is again strongly regular, with parameters (v, v − k − 1, v − 2k + μ − 2, v − 2k + λ).

Boring examples are obtained by putting a number of complete graphs next to each other. The union of m complete graphs, on w vertices each, is strongly regular with parameters v = mw, k = w−1, λ = w−2, μ = 0. The spectrum of such a graph is w−1 (m times), −1 (m(w−1) times).

Equally boring are the complements of these boring graphs, the complete multipartite graphs with m parts of size w. They have parameters v = mw, k = (m−1)w, λ = (m−2)w, μ = (m−1)w and spectrum (m−1)w (once), 0 (m(w−1) times), −w (m−1 times).

Below we are only interested in non-boring graphs, that is, we assume that 0 < μ < k.

There are precisely four non-boring strongly regular graphs on at most 12 vertices, and these have parameters (5,2,0,1), (9,4,1,2), (10,3,0,1) and (10,6,3,4). These are known as the pentagon, the 3×3 grid, the Petersen graph, and the triangular graph T(5). The first two are isomorphic to their complement, the last two are complementary.

The parameters of various infinite families of strongly regular graphs are given here.

References:

X. Hubaut, Strongly regular graphs, Discrete Math. 13 (1975) 357-381.

A.E. Brouwer & J.H van Lint, Strongly regular graphs and partial geometries, pp. 85-122 in: Enumeration and Design (D.M. Jackson & S.A. Vanstone, eds.), Academic Press, Toronto etc., 1984.

A.E. Brouwer, A.M. Cohen & A. Neumaier, Distance-regular graphs, Springer, Heidelberg, 1989.