In the mathematical field of graph theory, a distance-regular graph is a regular graph such that for any two vertices and , the number of vertices at distance from and at distance from depends only upon , , and the distance between and .
Some authors exclude the complete graphs and disconnected graphs from this definition.
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.
The intersection array of a distance-regular graph is the array in which is the diameter of the graph and for each , 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 . There is also the number that gives the number of neighbours of at distance from . The numbers are called the intersection numbers of the graph. They satisfy the equation where is the valency, i.e., the number of neighbours, of any vertex.
It turns out that a graph of diameter is distance regular if and only if it has an intersection array in the preceding sense.
A pair of connected distance-regular graphs are cospectral if their adjacency matrices have the same spectrum. This is equivalent to their having 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 connected distance-regular graph of valency with intersection array . For each let denote the number of vertices at distance from any given vertex and let denote the -regular graph with adjacency matrix formed by relating pairs of vertices on at distance .
If is strongly regular, then and .
The -distance adjacency matrices for of a distance-regular graph form an association scheme.
Some first examples of distance-regular graphs include:
There are only finitely many distinct connected distance-regular graphs of any given valency .
Similarly, there are only finitely many distinct connected distance-regular graphs with any given eigenvalue multiplicity (with the exception of the complete multipartite graphs).
The cubic distance-regular graphs have been completely classified.
The 13 distinct cubic distance-regular graphs are K<sub>4</sub> (or Tetrahedral graph), K<sub>3,3</sub>, the Petersen graph, the Cubical graph, the Heawood graph, the Pappus graph, the Coxeter graph, the TutteâÂÂCoxeter graph, the Dodecahedral graph, the Desargues graph, Tutte 12-cage, the BiggsâÂÂSmith graph, and the Foster graph.