DISTANCE-REGULAR GRAPH

In mathematics, a 'distance-regular graph' is a regular graph such that, given any two vertices ''v'' and ''w'' at any distance ''i'', the number of vertices adjacent to ''w'' and at distance ''j'' from ''v'' depends only on ''i'' and ''j'', not on the particular pair of vertices. 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).

Contents

Intersection numbers

Distance adjacency matrices

Examples

Classification

References

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''₀ = 1, ''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.
The numbers ''a_i'', ''b_i'', and ''c_i'' are often displayed in a three-line array
:
ight},
called the 'intersection array' of ''G''. They may also be formed into a tridiagonal matrix
:
c_1 & a_1 & b_1 & cdots & 0 & 0 \
0 & c_2 & a_2 & cdots & 0 & 0 \
dots & dots & dots & & dots & dots \
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:
:$A\; A\_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, 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''_2''d''+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.

Classification

There seems to be no hope of classifying all distance-regular graphs, desirable as that would be.

References

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