
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)".
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.
Intersection arrays.
It turns out that a graph formula_1 of diameter formula_2 is distance-regular if and only if there is an array of integers formula_3 such that for all formula_4, formula_5 gives the number of neighbours of formula_6 at distance formula_7 from formula_8 and formula_9 gives the number of neighbours of formula_6 at distance formula_11 from formula_8 for any pair of vertices formula_6 and formula_8 at distance formula_15 on formula_1. 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.
Properties.
Suppose formula_1 is a connected distance-regular graph of valency formula_18 with intersection array formula_3. For all formula_20: let formula_21 denote the formula_22-regular graph with adjacency matrix formula_23 formed by relating pairs of vertices on formula_1 at distance formula_15, and let formula_26 denote the number of neighbours of formula_6 at distance formula_15 from formula_8 for any pair of vertices formula_6 and formula_8 at distance formula_15 on formula_1. 
Spectral properties.
If formula_1 is strongly regular, then formula_52 and formula_53.
Examples.
Some first examples of distance-regular graphs include:
Classification of distance-regular graphs.
There are only finitely many distinct connected distance-regular graphs of any given valency formula_55.
Similarly, there are only finitely many distinct connected distance-regular graphs with any given eigenvalue multiplicity formula_56 (with the exception of the complete multipartite graphs).
Cubic distance-regular graphs.
The cubic distance-regular graphs have been completely classified.
The 13 distinct cubic distance-regular graphs are K4 (or Tetrahedral graph), K3,3, 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.