Distance-regular Graphs

In the mathematical field of graph theory, a distance-regular graph is a regular graph such that for any two vertices and , the number of vertices at distance from and at distance from depends only upon , , and the distance between and .

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

It turns out that a graph $G$ of diameter $d$ is distance-regular if and only if there is an array of integers $\$ such that for all $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$ on $G$. The array of integers characterizing a distance-regular graph is known as its intersection array.

Cospectral distance-regular graphs

A pair of connected distance-regular graphs are cospectral if and only if they have 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 $\$. For all $0 \leq j \leq d$: let $G_$ denote the $k_$-regular graph with adjacency matrix $A_j$ formed by relating pairs of vertices on $G$ at distance $j$, and let $a_j$ denote the number of neighbours of $u$ at distance $j$ from $v$ for any pair of vertices $u$ and $v$ at distance $j$ on $G$.

Graph-theoretic properties

* $\frac = \frac$ for all $0 \leq j < d$.
* $b_0 > b_1 \geq \cdots \geq b_ > 0$ and $1 = c_1 \leq \cdots \leq c_d \leq b_0$.

Spectral properties

*$k \leq \frac (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.
*$\lambda \in \$ if $\lambda$ is a simple eigenvalue of $G$.
*$G$ has $d + 1$ distinct eigenvalues.

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

Examples

Some first examples of distance-regular 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 $2$.

Classification of distance-regular graphs

There are only finitely many distinct connected distance-regular graphs of any given valency $k > 2$.

Similarly, there are only finitely many distinct connected distance-regular graphs with any given eigenvalue multiplicity $m > 2$ (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.

References

Further reading

*

{{DEFAULTSORT:Distance-Regular Graph
Algebraic graph theory
Graph families
Regular graphs