Distance-regular graph

Short description: Graph property

Graph families defined by their automorphisms
distance-transitive	→	distance-regular	←	strongly regular
↓
symmetric (arc-transitive)	←	t-transitive, t ≥ 2		skew-symmetric
↓
(if connected) vertex- and edge-transitive	→	edge-transitive and regular	→	edge-transitive
↓		↓		↓
vertex-transitive	→	regular	→	(if bipartite) biregular
↑
Cayley graph	←	zero-symmetric		asymmetric

In the mathematical field of graph theory, a distance-regular graph is a regular graph such that for any two vertices v and w, the number of vertices at distance j from v and at distance k from w depends only upon j, k, and the distance between v and 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 [math]\displaystyle{ ( b_0, b_1, \ldots, b_{d-1}; c_1, \ldots, c_d ) }[/math] in which [math]\displaystyle{ d }[/math] is the diameter of the graph and for each [math]\displaystyle{ 1 \leq j \leq d }[/math], [math]\displaystyle{ b_j }[/math] gives the number of neighbours of [math]\displaystyle{ u }[/math] at distance [math]\displaystyle{ j+1 }[/math] from [math]\displaystyle{ v }[/math] and [math]\displaystyle{ c_j }[/math] gives the number of neighbours of [math]\displaystyle{ u }[/math] at distance [math]\displaystyle{ j - 1 }[/math] from [math]\displaystyle{ v }[/math] for any pair of vertices [math]\displaystyle{ u }[/math] and [math]\displaystyle{ v }[/math] at distance [math]\displaystyle{ j }[/math]. There is also the number [math]\displaystyle{ a_j }[/math] that gives the number of neighbours of [math]\displaystyle{ u }[/math] at distance [math]\displaystyle{ j }[/math] from [math]\displaystyle{ v }[/math]. The numbers [math]\displaystyle{ a_j, b_j, c_j }[/math] are called the intersection numbers of the graph. They satisfy the equation [math]\displaystyle{ a_j + b_j + c_j = k, }[/math] where [math]\displaystyle{ k = b_0 }[/math] is the valency, i.e., the number of neighbours, of any vertex.

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

Graph-theoretic properties

• [math]\displaystyle{ \frac{k_{j+1}}{k_{j}} = \frac{b_{j}}{c_{j+1}} }[/math] for all [math]\displaystyle{ 0 \leq j \lt d }[/math].
• [math]\displaystyle{ b_0 \gt b_1 \geq \cdots \geq b_{d-1} \gt 0 }[/math] and [math]\displaystyle{ 1 = c_1 \leq \cdots \leq c_d \leq b_0 }[/math].

Spectral properties

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

If [math]\displaystyle{ G }[/math] is strongly regular, then [math]\displaystyle{ n \leq 4m - 1 }[/math] and [math]\displaystyle{ k \leq 2m - 1 }[/math].

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 of diameter [math]\displaystyle{ 2 }[/math].

Classification of distance-regular graphs

There are only finitely many distinct connected distance-regular graphs of any given valency [math]\displaystyle{ k \gt 2 }[/math].

Similarly, there are only finitely many distinct connected distance-regular graphs with any given eigenvalue multiplicity [math]\displaystyle{ m \gt 2 }[/math] (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

• Godsil, C. D. (1993). Algebraic Combinatorics. Chapman and Hall Mathematics Series. New York: Chapman and Hall. ISBN 978-0-412-04131-0.