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

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*, and

_{i}*c*, respectively; these are the

_{i}**intersection numbers**of

*G*. Obviously,

*a*

_{0}= 0,

*c*

_{0}= 0, and

*b*

_{0}equals

*k*, the degree of any vertex. If

*G*has finite diameter, then

*d*denotes the diameter and we have

*b*= 0. Also we have that

_{d}*a*

_{i}+b_{i}+c_{i}= kThe numbers *a _{i}*,

*b*, and

_{i}*c*are often displayed in a three-line array

_{i}called the **intersection array** of *G*. They may also be formed into a tridiagonal matrix

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*be the adjacency matrix of

_{i}*G*. For instance,

_{i}*A*

_{1}is the adjacency matrix

*A*of

*G*. Also, let

*A*

_{0}=

*I*, the identity matrix. This gives us

*d*+ 1 matrices

*A*

_{0},

*A*

_{1}, ..., A

*, called the*

_{d}**distance matrices**of

*G*. Their sum is the matrix

*J*in which every entry is 1. There is an important product formula:

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*of any two distance matrices is a linear combination of the distance matrices:

_{j}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_{4} (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

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