imported>Zaslav: /* Examples */ Clarify SRG example. + WP link.

2025-02-10T18:11:13Z

Examples: Clarify SRG example. + WP link.

New page

{{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 [[Vertex (graph theory)|vertices]] {{mvar|v}} and {{mvar|w}}, the number of vertices at [[distance (graph theory)|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 [[Graph automorphism|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 [[Degree (graph theory)|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 [[Spectral graph theory#Cospectral_graphs|cospectral]] if their [[Adjacency matrix|adjacency matrices]] have the same [[Spectrum of a matrix|spectrum]]. This is equivalent to their having the same intersection array.

A distance-regular graph is disconnected if and only if it is a [[Graph Union|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>k</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 graph|strongly regular]], then <math>n \leq 4m - 1</math> and <math>k \leq 2m - 1</math>.

==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 graph]]s.
* The [[cycle graph]]s.
* The [[odd graph]]s.
* The [[Moore graph]]s.
* The collinearity graph of a [[Near polygon#Regular near polygons|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 graph|cubic]] distance-regular graphs have been completely classified.

The 13 distinct cubic distance-regular graphs are [[complete graph|K<sub>4</sub>]] (or [[Tetrahedral graph]]), [[complete bipartite 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}}


==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]]

Distance-regular graph - Revision history

imported>Zaslav: /* Examples */ Clarify SRG example. + WP link.