Distance-regular graph

Graph families defined by their automorphisms
distance-transitive	${\boldsymbol {\rightarrow }}$	distance-regular	${\boldsymbol {\leftarrow }}$	strongly regular
${\boldsymbol {\downarrow }}$
symmetric (arc-transitive)	${\boldsymbol {\leftarrow }}$	t-transitive, t ≥ 2		skew-symmetric
${\boldsymbol {\downarrow }}$
_{(if connected)} vertex- and edge-transitive	${\boldsymbol {\rightarrow }}$	edge-transitive and regular	${\boldsymbol {\rightarrow }}$	edge-transitive
${\boldsymbol {\downarrow }}$		${\boldsymbol {\downarrow }}$		${\boldsymbol {\downarrow }}$
vertex-transitive	${\boldsymbol {\rightarrow }}$	regular	${\boldsymbol {\rightarrow }}$	_{(if bipartite)} biregular
${\boldsymbol {\uparrow }}$
Cayley graph	${\boldsymbol {\leftarrow }}$	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).

By considering the special case k = 1, one sees that in a distance-regular graph, for any two vertices v and w at distance i, the number of neighbors of w that are at distance j from v is the same. Conversely, it turns out that this special case implies the full definition of distance-regularity.^[1] Therefore, an equivalent definition is that a distance-regular graph is a regular graph for which there exist integers b_i,c_i,i=0,...,d such that for any two vertices x,y with y in G_i(x), there are exactly b_i neighbors of y in G_i-1(x) and c_i neighbors of y in G_i+1(x), where G_i(x) is the set of vertices y of G with d(x,y)=i (Brouwer et al., p. 434). The array of integers characterizing a distance-regular graph is known as its intersection array.

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.

A distance-regular graph with diameter 2 is strongly regular, and conversely (unless the graph is disconnected).

Intersection numbers

It is usual to use the following notation for a distance-regular graph G. The number of vertices is n. The number of neighbors of w (that is, vertices adjacent to w) whose distance from v is i, i + 1, and i − 1 is denoted by a_i, b_i, and c_i, respectively; these are the intersection numbers of G. Obviously, a₀ = 0, c₀ = 0, and b₀ equals k, the degree of any vertex. If G has finite diameter, then d denotes the diameter and we have b_d = 0. Also we have that a_i+b_i+c_i= k

The numbers a_i, b_i, and c_i are often displayed in a three-line array

\left\{{\begin{matrix}-&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}}&-\end{matrix}}\right\},

called the intersection array of G. They may also be formed into a tridiagonal matrix

B:={\begin{pmatrix}a_{0}&b_{0}&0&\cdots &0&0\\c_{1}&a_{1}&b_{1}&\cdots &0&0\\0&c_{2}&a_{2}&\cdots &0&0\\\vdots &\vdots &\vdots &&\vdots &\vdots \\0&0&0&\cdots &a_{{d-1}}&b_{{d-1}}\\0&0&0&\cdots &c_{d}&a_{d}\end{pmatrix}},

called the intersection matrix.

Distance adjacency matrices

Suppose G is a connected distance-regular graph. For each distance i = 1, ..., d, we can form a graph G_i in which vertices are adjacent if their distance in G equals i. Let A_i be the adjacency matrix of G_i. For instance, A₁ is the adjacency matrix A of G. Also, let A₀ = I, the identity matrix. This gives us d + 1 matrices A₀, A₁, ..., A_d, called the distance matrices of G. Their sum is the matrix J in which every entry is 1. There is an important product formula:

AA_{i}=a_{i}A_{i}+b_{i}A_{{i+1}}+c_{i}A_{{i-1}}.

From this formula it follows that each A_i is a polynomial function of A, of degree i, and that A satisfies a polynomial of degree d + 1. Furthermore, A has exactly d + 1 distinct eigenvalues, namely the eigenvalues of the intersection matrix B,of which the largest is k, the degree.

The distance matrices span a vector subspace of the vector space of all n × n real matrices. It is a remarkable fact that the product A_i A_j of any two distance matrices is a linear combination of the distance matrices:

A_{i}A_{j}=\sum _{{k=0}}^{d}p_{{ij}}^{k}A_{k}.

This means that the distance matrices generate an association scheme. The theory of association schemes is central to the study of distance-regular graphs. For instance, the fact that A_i is a polynomial function of A is a fact about association schemes.

Examples

Complete graphs are distance regular with diameter 1 and degree v−1.
Cycles C_n are distance regular with k = 2, for all n > 2.
All Moore graphs, in particular the Petersen graph and the Hoffman-Singleton graph, are distance regular.
The Wells graph and Sylvester graph.
Strongly regular graphs are distance regular.
The odd graphs are distance regular.
The collinearity graph of every regular near polygon is distance-regular.

Cubic distance-regular graphs

There are 13 distance-regular cubic graphs: 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.

Notes

↑ A.E. Brouwer, A.M. Cohen, and A. Neumaier (1989), Distance Regular Graphs. Berlin, New York: Springer-Verlag. ISBN 3-540-50619-5, ISBN 0-387-50619-5