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 $G$ of diameter $d$ is distance-regular if and only if there is an array of integers $\{b_{0},b_{1},\cdots ,b_{d-1};c_{1},\cdots ,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 distance-regular graph with intersection array $\{b_{0},b_{1},\cdots ,b_{d-1};c_{1},\cdots ,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}$.

Algebraic properties

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

Intersection matrices

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

$AX=XB$

where $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 $B$ is the minimal polynomial of $A$.

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 connected distance-regular graphs of valency $k$ for all $k\geq 3$.

Cubic distance-regular graphs

The cubic distance-regular graphs have been completely classified.

The 13 distinct cubic distance-regular graphs are K₄ (or tetrahedron), K_3,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.

Further reading

• Godsil, C. D. (1993). Algebraic combinatorics. Chapman and Hall Mathematics Series. New York: Chapman and Hall. pp. xvi+362. ISBN 0-412-04131-6. MR 1220704. {{cite book}}: Invalid |ref=harv (help)