An introduction to distance-regular graphs

Suppose that $\Gamma$ is a graph on $n$ vertices with diameter $d$. For any vertex $u$ and for any integer $i$ with $0\leq i\leq d$, let $\Gamma_i(u)$ denote the set of vertices at distance $i$ from $u$.

If $v\in\Gamma_i(u)$ and $w$ is a neighbour of $v$, then $w$ must be at distance $i-1$, $i$ or $i+1$ from $u$. Let $c_i$, $a_i$ and $b_i$ denote the number of such vertices $w$.

We call $\Gamma$ a distance-regular graph if and only if these parameters $c_i,a_i,b_i$ depends only on the distance $i$, and not on the choice of $u$ and $v$.

We put the parameters $c_i,a_i,b_i$ into an array, the intersection array of $\Gamma$, as follows:

$\left\{ \begin{array}{ccccc} \ast & c_1 & \cdots & c_{d-1} & c_d \\ a_0 & a_1 & \cdots & a_{d-1} & a_d \\ b_0 & b_1 & \cdots & b_{d-1} & \ast \end{array} \right\}$.

It is straightforward to see that $c_0$ and $b_d$ are undefined, $a_0=0$, $c_1=1$ and that $b_0$ is the valency (degree) of any vertex, so we let $b_0=k$, the valency of the graph. It is also straightforward to see that $c_i+a_i+b_i=k$ for each $i$, so the middle row of the array is redundant. Consequently, the intersection array is often abbreviated as follows:

$\{k,b_1,\ldots,b_{d-1};\, 1,c_2,\ldots,c_d\}$.

Strongly regular and distance-transitive graphs

There are two particularly important sub-classes of distance-regular graphs.

First, a graph $\Gamma$ on $n$ vertices with valency $k$ is called a strongly regular graph with parameters $(n,k,\lambda,\mu)$ if any pair of adjacent vertices have $\lambda$ common neighbours, and any pair of non-adjacent vertices have $\mu$ common neighbours. A connected strongly regular graph has diameter at most two: the diameter-1 examples are complete graphs, while the diameter-2 examples are precisely the diameter-2 distance-regular graphs; we have $b_0=k$, $a_1=\lambda$ and $c_2=\mu$.

Second, a graph is a distance-transitive graph if, for any distance $i$ and for two pairs of vertices $(u_1,v_1)$ and $(u_2,v_2)$ at distance $i$, there exists an automorphism of $\Gamma$ mapping $u_1$ to $u_2$ and $v_1$ to $v_2$. Since automorphisms preserve distances, it follows from this definition that if $\Gamma$ is distance-transitive, then it must also be distance-regular. (The converse is far from true: the smallest distance-regular graph that is not distance-transitive is the Shrikhande graph on 16 vertices.)

Primitive and imprimitive graphs

Suppose that $\Gamma$ is a distance-regular graph. We say that $\Gamma$ is primitive if, for each $i$ with $1\leq i \leq d$, the distance-$i$ graphs of $\Gamma$ are all connected. Otherwise, we say that $\Gamma$ is imprimitive. In the case that $\Gamma$ is distance-transitive, $\Gamma$ being primitive is equivalent to the action of $\mathrm{Aut}(\Gamma)$ being primitive (in the sense of permutation groups) on the vertices of $\Gamma$.

It turns out that there are only two ways in which a distance-regular graph can be imprimitive: it can either be bipartite (where the distance-2 graph has two connected components), or antipodal (where the distance-$d$ graph is a disjoint union of complete graphs, meaning that if $v\in\Gamma_d(u)$ and $w\in\Gamma_d(u)$ are distinct, then $v$ and $w$ are also at distance $d$). It is possible for a graph to be simultaneously bipartite and antipodal (for instance, the hypercubes).

Unexciting examples

The complete graphs $K_n$, complete bipartite graphs $K_{n,n}$, complete multipartite graphs $rK_m$, and cycles $C_n$ are all distance-regular graphs. These examples are sufficiently unexciting that they cannot be found on this site!

Robert Bailey, 3 August 2017