Distance-regular graph

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

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,\dots ,b_{d-1};c_1,\dots ,c_d)$ in which $d$ is the diameter of the graph and for each $1\le j\le 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,\dots ,b_{d-1};c_1,\dots ,c_d)$. For each $0\le j\le 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\le j<d$.
• $b_0>b_1\ge \cdots \ge b_{d-1}>0$ and $1=c_1\le \cdots \le c_d\le 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\le \frac{1}{2}(m-1)(m+2)$ for any eigenvalue multiplicity $m>1$ of $G,$ unless $G$ is a complete multipartite graph.
• $d\le 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\le 4m-1$ and $k\le 2m-1$.

Examples

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 $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.

Further reading

• Template:Cite book