Distance-regular graph

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Graph families defined by their automorphisms
distance-transitive \boldsymbol{\rightarrow} distance-regular \boldsymbol{\leftarrow} strongly regular
symmetric (arc-transitive) \boldsymbol{\leftarrow} t-transitive, t ≥ 2
(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)
Cayley graph skew-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 bi,ci,i=0,...,d such that for any two vertices x,y with y in Gi(x), there are exactly bi neighbors of y in Gi-1(x) and ci neighbors of y in Gi+1(x), where Gi(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[edit]

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 ai, bi, and ci, respectively; these are the intersection numbers of G. Obviously, a0 = 0, c0 = 0, and b0 equals k, the degree of any vertex. If G has finite diameter, then d denotes the diameter and we have bd = 0. Also we have that ai+bi+ci= k

The numbers ai, bi, and ci 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[edit]

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

A A_i = a_i A_i + b_i A_{i+1} + c_i A_{i-1} .

From this formula it follows that each Ai 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 Ai Aj 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 Ai is a polynomial function of A is a fact about association schemes.


Cubic distance-regular graphs[edit]

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


  1. ^ 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[edit]