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).

In particular, this holds when k = 1: in a distance-regular graph, for any two vertices v and w at distance i the number of vertices adjacent to w and at distance j from v is the same. It turns out that, conversely, this implies the above definition of distance-regularity. Therefore, an equivalent definition is that a distance-regular graph is a graph for which there exist integers b_i,c_i,i=0,...,d such that for any two vertices x,y in G and distance i=d(x,y), there are exactly c_i neighbors of y in G_i-1(x) and b_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_2d+1 of odd length are distance regular with k = 2 and diameter d. The intersection numbers a_i = 0, b_i = 1, and c_i = 1, except for the usual special cases (see above) and c_d = 2.
• All Moore graphs, in particular the Petersen graph and the Hoffman-Singleton graph, are distance regular.
• Strongly regular graphs are distance regular.
• The odd graphs are distance regular.

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)