Distance-regular graph

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 $( b_0, b_1, \ldots, b_{d-1}; c_1, \ldots, c_d )$ in which $d$ is the diameter of the graph and for each $1 \leq j \leq d$ , $b_j$ gives the number of neighbours of $u$ at distance $j+1$ from $v$ and $c_j$ gives the number of neighbours of $u$ at distance $j - 1$ from $v$ for any pair of vertices $u$ and $v$ at distance $j$ . There is also the number $a_j$ that gives the number of neighbours of $u$ at distance $j$ from $v$ . The numbers $a_j, b_j, c_j$ are called the intersection numbers of the graph. They satisfy the equation $a_j + b_j + c_j = k,$ where $k = b_0$ is the valency, i.e., the number of neighbours, of any vertex.

It turns out that a graph $G$ of diameter $d$ 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 $G$ is a connected distance-regular graph of valency $k$ with intersection array $( b_0, b_1, \ldots, b_{d-1}; c_1, \ldots, c_d )$ . For each $0 \leq j \leq d,$ let $k_j$ denote the number of vertices at distance $k$ from any given vertex and let $G_{j}$ denote the $k_{j}$ -regular graph with adjacency matrix $A_j$ formed by relating pairs of vertices on $G$ at distance $j$ .

= Graph-theoretic properties =

$\frac{k_{j+1}}{k_{j}} = \frac{b_{j}}{c_{j+1}}$ for all $0 \leq j < d$ .
$b_0 > b_1 \geq \cdots \geq b_{d-1} > 0$ and $1 = c_1 \leq \cdots \leq c_d \leq b_0$ .

= Spectral properties =

$G$ has $d + 1$ distinct eigenvalues.
The only simple eigenvalue of $G$ is $k,$ or both $k$ and $-k$ if $G$ is bipartite.
$k \leq \frac{1}{2} (m - 1)(m + 2)$ for any eigenvalue multiplicity $m > 1$ of $G,$ unless $G$ is a complete multipartite graph.
$d \leq 3m - 4$ for any eigenvalue multiplicity $m > 1$ of $G,$ unless $G$ is a cycle graph or a complete multipartite graph.

If $G$ is strongly regular, then $n \leq 4m - 1$ and $k \leq 2m - 1$ .

Examples

File:Klein-map.png 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 $k > 2$ .{{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}}

Similarly, there are only finitely many distinct connected distance-regular graphs with any given eigenvalue multiplicity $m > 2$ {{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}} (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₄ (or Tetrahedral graph), K_3,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.