# Distance-regular graph

Graph families defined by their automorphisms
distance-transitive distance-regular strongly regular
symmetric (arc-transitive) t-transitive, t ≥ 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

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 ${\displaystyle G}$ of diameter ${\displaystyle d}$ is distance-regular if and only if there is an array of integers ${\displaystyle \{b_{0},b_{1},\cdots ,b_{d-1};c_{1},\cdots ,c_{d}\}}$ such that for all ${\displaystyle 1\leq j\leq d}$, ${\displaystyle b_{j}}$ gives the number of neighbours of ${\displaystyle u}$ at distance ${\displaystyle j+1}$ from ${\displaystyle v}$ and ${\displaystyle c_{j}}$ gives the number of neighbours of ${\displaystyle u}$ at distance ${\displaystyle j-1}$ from ${\displaystyle v}$ for any pair of vertices ${\displaystyle u}$ and ${\displaystyle v}$ at distance ${\displaystyle j}$ on ${\displaystyle 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 ${\displaystyle G}$ is a connected distance-regular graph with intersection array ${\displaystyle \{b_{0},b_{1},\cdots ,b_{d-1};c_{1},\cdots ,c_{d}\}}$. For all ${\displaystyle 0\leq j\leq d}$: let ${\displaystyle G_{j}}$ denote the ${\displaystyle k_{j}}$-regular graph with adjacency matrix ${\displaystyle A_{j}}$ formed by relating pairs of vertices on ${\displaystyle G}$ at distance ${\displaystyle j}$, and let ${\displaystyle a_{j}}$ denote the number of neighbours of ${\displaystyle u}$ at distance ${\displaystyle j}$ from ${\displaystyle v}$ for any pair of vertices ${\displaystyle u}$ and ${\displaystyle v}$ at distance ${\displaystyle j}$ on ${\displaystyle G}$.

### Graph-theoretic properties

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

### Algebraic properties

• ${\displaystyle AA_{j}=c_{j+1}A_{j+1}+a_{j}A_{j}+b_{j-1}A_{j-1}}$ for all ${\displaystyle 0.
• The adjacency algebra of ${\displaystyle G}$ is the Bose–Mesner algebra of an association scheme where pairs of vertices on ${\displaystyle G}$ are related by their distance; moreover, ${\displaystyle G}$ has ${\displaystyle d+1}$ distinct eigenvalues.

#### Intersection matrices

There is a tridiagonal matrix ${\displaystyle B}$, called the intersection matrix of ${\displaystyle G}$, such that for any vertex ${\displaystyle v}$ on ${\displaystyle G}$:

${\displaystyle AX=XB}$

where ${\displaystyle X:={\begin{bmatrix}e_{v}\mid Ae_{v}\mid A_{2}e_{v}\mid \cdots \mid \cdots \mid A_{d}e_{v}\end{bmatrix}}}$.

The characteristic polynomial of ${\displaystyle B}$ is the minimal polynomial of ${\displaystyle A}$.

## Examples

Some first examples of distance-regular graphs include:

## Classification of distance-regular graphs

There are only finitely many connected distance-regular graphs of valency ${\displaystyle k}$ for all ${\displaystyle k\geq 3}$.[1]

There are only finitely many connected distance-regular graphs with an eigenvalue multiplicity ${\displaystyle m}$ for all ${\displaystyle m\geq 2.}$[2]

### Cubic distance-regular graphs

The cubic distance-regular graphs have been completely classified.

The 13 distinct cubic distance-regular graphs are K4 (or tetrahedron), K3,3, the Petersen graph, the cube, the Heawood graph, the Pappus graph, the Coxeter graph, the Tutte–Coxeter graph, the dodecahedron, the Desargues graph, Tutte 12-cage, the Biggs–Smith graph, and the Foster graph.

## References

1. ^ 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:. doi:10.1016/j.aim.2014.09.025.
2. ^ 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.