Distance-regular graph explained

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 .

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

(k _{j+1})/(k _{j}) = (b _{j})/(c _{j+1}) for all 0 \leq j < d .b _{0} > b _{1} \geq … \geq b _{d-1} > 0 and 1 = c _{1} \leq … \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 (1)/(2) (m - 1 )(m + 2 ) for any eigenvalue multiplicity m > 1 of G, unless G is a complete multipartite graph.d \leq 3 m - 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 4 m - 1 and k \leq 2 m - 1 .

Examples

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

2 .

Classification of distance-regular graphs

There are only finitely many distinct connected distance-regular graphs of any given valency

k > 2 .^[1]

Similarly, there are only finitely many distinct connected distance-regular graphs with any given eigenvalue multiplicity

m > 2 ^[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

• Book: Godsil, C.&nbsp;D.. Chris Godsil. Algebraic Combinatorics. Chapman and Hall Mathematics Series. Chapman and Hall. New York. 1993. 978-0-412-04131-0. 1220704.

Notes and References

1. Bang. S.. Dubickas. A.. Koolen. J. H.. Moulton. V.. 2015-01-10. There are only finitely many distance-regular graphs of fixed valency greater than two. Advances in Mathematics. 269. Supplement C. 1–55. 10.1016/j.aim.2014.09.025. free. 0909.5253. 18869283.
2. Godsil. C. D.. 1988-12-01. Bounding the diameter of distance-regular graphs. Combinatorica. en. 8. 4. 333–343. 10.1007/BF02189090. 206813795. 0209-9683.