This article needs additional citations for verification. (June 2009) (Learn how and when to remove this template message)
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).
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.
It turns out that a graph of diameter is distance-regular if and only if there is an array of integers such that for all , gives the number of neighbours of at distance from and gives the number of neighbours of at distance from for any pair of vertices and at distance on . The array of integers characterizing a distance-regular graph is known as its intersection array.
Cospectral distance-regular graphs
A pair of connected distance-regular graphs are cospectral if and only if they have the same intersection array.
A distance-regular graph is disconnected if and only if it is a disjoint union of cospectral distance-regular graphs.
Suppose is a distance-regular graph with intersection array . For all : let denote the -regular graph with adjacency matrix formed by relating pairs of vertices on at distance , and let denote the number of neighbours of at distance from for any pair of vertices and at distance on .
- for all .
- and .
- for all .
- The adjacency algebra of is the Bose-Mesner algebra of an association scheme where pairs of vertices on are related by their distance; moreover, has distinct eigenvalues if it is connected.
There is a tridiagonal matrix , called the intersection matrix of , such that for any vertex on :
Some first examples of distance-regular graphs include:
- The complete graphs.
- The cycles graphs.
- The odd graphs.
- The Moore graphs.
- The collinearity graph of a regular near polygon.
- The Wells graph and the Sylvester graph.
- Strongly regular graphs of diameter .
Classification of distance-regular graphs
There are only finitely many connected distance-regular graphs of valency for all .
Cubic distance-regular graphs
The cubic distance-regular graphs have been completely classified.
The 13 distinct cubic distance-regular graphs are 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.
- Bang, S.; Dubickas, A.; Koolen, J. H.; Moulton, V. (2015-01-10). "There are only finitely many distance-regular graphs of fixed valency greater than two". Advances in Mathematics. 269 (Supplement C): 1–55. doi:10.1016/j.aim.2014.09.025.