Distanceregular graph
This article needs additional citations for verification. (June 2009) (Learn how and when to remove this template message)

Graph families defined by their automorphisms  

distancetransitive  →  distanceregular  ←  strongly regular 
↓  
symmetric (arctransitive)  ←  ttransitive, t ≥ 2  skewsymmetric  
↓  
_{(if connected)} vertex and edgetransitive 
→  edgetransitive and regular  →  edgetransitive 
↓  ↓  ↓  
vertextransitive  →  regular  → 
_{(if bipartite)} biregular 
↑  
Cayley graph  ←  zerosymmetric  asymmetric 
In mathematics, a distanceregular 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 distancetransitive graph is distanceregular. Indeed, distanceregular graphs were introduced as a combinatorial generalization of distancetransitive graphs, having the numerical regularity properties of the latter without necessarily having a large automorphism group.
Contents
Intersection arrays
It turns out that a graph of diameter is distanceregular 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 distanceregular graph is known as its intersection array.
Cospectral distanceregular graphs
A pair of connected distanceregular graphs are cospectral if and only if they have the same intersection array.
A distanceregular graph is disconnected if and only if it is a disjoint union of cospectral distanceregular graphs.
Properties
Suppose is a connected distanceregular graph of valency 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 .
Graphtheoretic properties
 for all .
 and .
Spectral properties
 for any eigenvalue multiplicity of , unless is a complete multipartite graph.
 for any eigenvalue multiplicity of , unless is a cycle graph or a complete multipartite graph.
 if is a simple eigenvalue of .
 has distinct eigenvalues.
If is strongly regular, then and .
Examples
Some first examples of distanceregular 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 distanceregular graphs
There are only finitely many distinct connected distanceregular graphs of any given valency .^{[1]}
Similarly, there are only finitely many distinct connected distanceregular graphs with any given eigenvalue multiplicity ^{[2]} (with the exception of the complete multipartite graphs).
Cubic distanceregular graphs
The cubic distanceregular graphs have been completely classified.
The 13 distinct cubic distanceregular graphs are K_{4} (or tetrahedron), K_{3,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 12cage, the Biggs–Smith graph, and the Foster graph.
References
 ^ Bang, S.; Dubickas, A.; Koolen, J. H.; Moulton, V. (20150110). "There are only finitely many distanceregular graphs of fixed valency greater than two". Advances in Mathematics. 269 (Supplement C): 1–55. arXiv:0909.5253 . doi:10.1016/j.aim.2014.09.025.
 ^ Godsil, C. D. (19881201). "Bounding the diameter of distanceregular graphs". Combinatorica. 8 (4): 333–343. doi:10.1007/BF02189090. ISSN 02099683.
Further reading
 Godsil, C. D. (1993). Algebraic combinatorics. Chapman and Hall Mathematics Series. New York: Chapman and Hall. pp. xvi+362. ISBN 0412041316. MR 1220704.