Distance-regular graph

In mathematics, a distance-regular graph is a regular graph such that for any two vertices v and w, the number of vertices at distance j from v and at distance k from w depends only upon j, k, and i = d(v, w).

Every distance-transitive graph is distance-regular. Indeed, distance-regular graphs were introduced as a combinatorial generalization of distance-transitive graphs, having the numerical regularity properties of the latter without necessarily having a large automorphism group.

Intersection arrays

It turns out that a graph $G$ of diameter $d$ is distance-regular if and only if there is an array of integers $\{b_{0},b_{1},\ldots ,b_{d-1};c_{1},\ldots ,c_{d}\}$ such that for all $1\leq j\leq d$ , $b_{j}$ gives the number of neighbours of $u$ at distance $j+1$ from $v$ and $c_{j}$ gives the number of neighbours of $u$ at distance $j-1$ from $v$ for any pair of vertices $u$ and $v$ at distance $j$ on $G$ . The array of integers characterizing a distance-regular graph is known as its intersection array.

Cospectral distance-regular graphs

A pair of connected distance-regular graphs are cospectral if and only if they have the same intersection array.

A distance-regular graph is disconnected if and only if it is a disjoint union of cospectral distance-regular graphs.

Properties

Suppose $G$ is a connected distance-regular graph of valency $k$ with intersection array $\{b_{0},b_{1},\ldots ,b_{d-1};c_{1},\ldots ,c_{d}\}$ . For all $0\leq j\leq d$ : let $G_{j}$ denote the $k_{j}$ -regular graph with adjacency matrix $A_{j}$ formed by relating pairs of vertices on $G$ at distance $j$ , and let $a_{j}$ denote the number of neighbours of $u$ at distance $j$ from $v$ for any pair of vertices $u$ and $v$ at distance $j$ on $G$ .

Graph-theoretic properties

${\frac {k_{j+1}}{k_{j}}}={\frac {b_{j}}{c_{j+1}}}$ for all $0\leq j<d$ .
$b_{0}>b_{1}\geq \cdots \geq b_{d-1}>0$ and $1=c_{1}\leq \cdots \leq c_{d}\leq b_{0}$ .

Spectral properties

$k\leq {\frac {1}{2}}(m-1)(m+2)$ for any eigenvalue multiplicity $m>1$ of $G$ , unless $G$ is a complete multipartite graph.
$d\leq 3m-4$ for any eigenvalue multiplicity $m>1$ of $G$ , unless $G$ is a cycle graph or a complete multipartite graph.
$\lambda \in \{\pm k\}$ if $\lambda$ is a simple eigenvalue of $G$ .
$G$ has $d+1$ distinct eigenvalues.

If $G$ is strongly regular, then $n\leq 4m-1$ and $k\leq 2m-1$ .

Examples

Some first examples of distance-regular graphs include:

The complete graphs.
The cycles graphs.
The odd graphs.
The Moore graphs.
The collinearity graph of a regular near polygon.
The Wells graph and the Sylvester graph.
Strongly regular graphs of diameter $2$ .

Classification of distance-regular graphs

There are only finitely many distinct connected distance-regular graphs of any given valency $k>2$ .^[1]

Similarly, there are only finitely many distinct connected distance-regular graphs with any given eigenvalue multiplicity $m > 2$ ^[2] (with the exception of the complete multipartite graphs).

Cubic distance-regular graphs

The cubic distance-regular graphs have been completely classified.

The 13 distinct cubic distance-regular graphs are K₄ (or Tetrahedral graph), K_3,3, the Petersen graph, the Cubical graph, the Heawood graph, the Pappus graph, the Coxeter graph, the Tutte–Coxeter graph, the Dodecahedral graph, the Desargues graph, Tutte 12-cage, the Biggs–Smith graph, and the Foster graph.

References

^ Bang, S.; Dubickas, A.; Koolen, J. H.; Moulton, V. (2015-01-10). "There are only finitely many distance-regular graphs of fixed valency greater than two". Advances in Mathematics. 269 (Supplement C): 1–55. arXiv:0909.5253. doi:10.1016/j.aim.2014.09.025.
^ Godsil, C. D. (1988-12-01). "Bounding the diameter of distance-regular graphs". Combinatorica. 8 (4): 333–343. doi:10.1007/BF02189090. ISSN 0209-9683.

Graph families defined by their automorphisms
distance-transitive	→	distance-regular	←	strongly regular
↓
symmetric (arc-transitive)	←	t-transitive, $t \geq 2$		skew-symmetric
↓
_{(if connected)} vertex- and edge-transitive	→	edge-transitive and regular	→	edge-transitive
↓		↓		↓
vertex-transitive	→	regular	→	_{(if bipartite)} biregular
↑
Cayley graph	←	zero-symmetric		asymmetric