# Distance-regular graph

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Distance-regular_graph
> Markdown URL: https://mediated.wiki/source/Distance-regular_graph.md
> Source: https://en.wikipedia.org/wiki/Distance-regular_graph
> Source revision: 1326563603
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{short description|Graph property}}
{{refimprove|date=June 2009}}
{{Graph families defined by their automorphisms}}

In the [mathematical](/source/mathematical) field of [graph theory](/source/graph_theory), a '''distance-regular graph''' is a [regular graph](/source/regular_graph) such that for any two [vertices](/source/Vertex_(graph_theory)) {{mvar|v}} and {{mvar|w}}, the number of vertices at [distance](/source/distance_(graph_theory)) {{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](/source/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](/source/Graph_automorphism).

==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](/source/Degree_(graph_theory)), 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](/source/Spectral_graph_theory) if their [adjacency matrices](/source/Adjacency_matrix) have the same [spectrum](/source/Spectrum_of_a_matrix).  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](/source/Graph_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](/source/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](/source/Strongly_regular_graph), 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](/source/association_scheme).

==Examples==
[[File:Klein-map.png|thumb|The degree 7 [Klein graph](/source/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 graph](/source/complete_graph)s.
* The [cycle graph](/source/cycle_graph)s. 
* The [odd graph](/source/odd_graph)s. 
* The [Moore graph](/source/Moore_graph)s. 
* The collinearity graph of a [regular near polygon](/source/Near_polygon).
* The [Wells graph](/source/Wells_graph) and the [Sylvester graph](/source/Sylvester_graph).
* [Strongly regular graphs](/source/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](/source/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](/source/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](/source/Cubic_graph) distance-regular graphs have been completely classified.

The 13 distinct cubic distance-regular graphs are [K<sub>4</sub>](/source/complete_graph) (or [Tetrahedral graph](/source/Tetrahedral_graph)), [K<sub>3,3</sub>](/source/complete_bipartite_graph), the [Petersen graph](/source/Petersen_graph), the [Cubical graph](/source/Cubical_graph), the [Heawood graph](/source/Heawood_graph), the [Pappus graph](/source/Pappus_graph), the [Coxeter graph](/source/Coxeter_graph), the [Tutte–Coxeter graph](/source/Tutte%E2%80%93Coxeter_graph), the [Dodecahedral graph](/source/Dodecahedral_graph), the [Desargues graph](/source/Desargues_graph), [Tutte 12-cage](/source/Tutte_12-cage), the [Biggs–Smith graph](/source/Biggs%E2%80%93Smith_graph), and the [Foster graph](/source/Foster_graph).

==References==
{{Reflist}}

<!-- ==References== -->
==Further reading==
*  {{cite book|last=Godsil|first=C.&nbsp;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

---
Adapted from the Wikipedia article [Distance-regular graph](https://en.wikipedia.org/wiki/Distance-regular_graph) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Distance-regular_graph?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.