{{short description|Graph property}} {{refimprove|date=June 2009}} {{Graph families defined by their automorphisms}}
In the mathematical field of graph theory, a '''distance-regular graph''' is a regular graph such that for any two vertices {{mvar|v}} and {{mvar|w}}, the number of vertices at distance {{mvar|j}} from {{mvar|v}} and at distance {{mvar|k}} from {{mvar|w}} depends only upon {{mvar|j}}, {{mvar|k}}, and the distance between {{mvar|v}} and {{mvar|w}}.
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.
==Intersection arrays==
The '''intersection array''' of a distance-regular graph is the array <math>( b_0, b_1, \ldots, b_{d-1}; c_1, \ldots, c_d ) </math> in which <math>d</math> is the diameter of the graph and for each <math>1 \leq j \leq d </math>, <math>b_j </math> gives the number of neighbours of <math>u </math> at distance <math>j+1 </math> from <math>v </math> and <math>c_j </math> gives the number of neighbours of <math>u </math> at distance <math>j - 1 </math> from <math>v </math> for any pair of vertices <math>u </math> and <math>v </math> at distance <math>j </math>. There is also the number <math>a_j</math> that gives the number of neighbours of <math>u </math> at distance <math>j </math> from <math>v </math>. The numbers <math>a_j, b_j, c_j</math> are called the '''intersection numbers''' of the graph. They satisfy the equation <math>a_j + b_j + c_j = k,</math> where <math>k = b_0</math> is the valency, i.e., the number of neighbours, of any vertex.
It turns out that a graph <math>G </math> of diameter <math>d </math> is distance regular if and only if it has an intersection array in the preceding sense.
== Cospectral and disconnected distance-regular graphs == 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.
==Properties==
Suppose <math>G </math> is a connected distance-regular graph of valency <math>k</math> with intersection array <math>( b_0, b_1, \ldots, b_{d-1}; c_1, \ldots, c_d ) </math>. For each <math>0 \leq j \leq d, </math> let <math>k_j</math> denote the number of vertices at distance <math>j</math> from any given vertex and let <math>G_{j} </math> denote the <math>k_{j} </math>-regular graph with adjacency matrix <math>A_j </math> formed by relating pairs of vertices on <math>G </math> at distance <math>j </math>.
=== Graph-theoretic properties === * <math>\frac{k_{j+1}}{k_{j}} = \frac{b_{j}}{c_{j+1}} </math> for all <math>0 \leq j < d </math>. * <math>b_0 > b_1 \geq \cdots \geq b_{d-1} > 0 </math> and <math>1 = c_1 \leq \cdots \leq c_d \leq b_0 </math>.
=== Spectral properties === *<math>G </math> has <math>d + 1 </math> distinct eigenvalues. *The only simple eigenvalue of <math>G </math> is <math>k,</math> or both <math>k</math> and <math>-k</math> if <math>G</math> is bipartite. *<math>k \leq \frac{1}{2} (m - 1)(m + 2)</math> for any eigenvalue multiplicity <math>m > 1</math> of <math>G,</math> unless <math>G</math> is a complete multipartite graph. *<math>d \leq 3m - 4</math> for any eigenvalue multiplicity <math>m > 1</math> of <math>G,</math> unless <math>G</math> is a cycle graph or a complete multipartite graph.
If <math>G </math> is strongly regular, then <math>n \leq 4m - 1</math> and <math>k \leq 2m - 1</math>.
=== Association scheme === The <math>i</math>-distance adjacency matrices <math>A_i</math> for <math>i = 0, 1, ..., d</math> of a distance-regular graph form an association scheme.
==Examples== [[File:Klein-map.png|thumb|The degree 7 Klein graph and associated map embedded in an orientable surface of genus 3. This graph is distance regular with intersection array {7,4,1;1,2,7} and automorphism group PGL(2,7).]] Some first examples of distance-regular graphs include: * The complete graphs. * The cycle 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 are the distance-regular graphs of diameter 2.
== Classification of distance-regular graphs == There are only finitely many distinct connected distance-regular graphs of any given valency <math>k > 2</math>.<ref>{{Cite journal|last1=Bang|first1=S.|last2=Dubickas|first2=A.|last3=Koolen|first3=J. H.|last4=Moulton|first4=V.|date=2015-01-10|title=There are only finitely many distance-regular graphs of fixed valency greater than two|journal=Advances in Mathematics|volume=269|issue=Supplement C|pages=1–55|doi=10.1016/j.aim.2014.09.025|doi-access=free|arxiv=0909.5253|s2cid=18869283}}</ref>
Similarly, there are only finitely many distinct connected distance-regular graphs with any given eigenvalue multiplicity <math>m > 2</math><ref>{{Cite journal|last=Godsil|first=C. D.|date=1988-12-01|title=Bounding the diameter of distance-regular graphs|journal=Combinatorica|language=en|volume=8|issue=4|pages=333–343|doi=10.1007/BF02189090|s2cid=206813795|issn=0209-9683}}</ref> (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 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.
==References== {{Reflist}}
<!-- ==References== --> ==Further reading== * {{cite book|last=Godsil|first=C. D.|author-link=Chris Godsil|title=Algebraic Combinatorics|series=Chapman and Hall Mathematics Series|publisher=Chapman and Hall|location=New York|year=1993|isbn=978-0-412-04131-0|mr=1220704}}
{{DEFAULTSORT:Distance-Regular Graph}} Category:Algebraic graph theory Category:Graph families Category:Regular graphs