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 are called the intersection numbers is the valency, i.e., the number of neighbours, of any vertex.

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

-regular graph with adjacency matrix.

Graph-theoretic properties

• .

• .

Spectral properties

• distinct eigenvalues.

• is bipartite.

• is a complete multipartite graph.

• is a cycle graph or a complete multipartite graph.

is strongly regular.

Association scheme

of a distance-regular graph form an association scheme.

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 are the distance-regular graphs of diameter 2.

Classification of distance-regular graphs

.

(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 K4 (or Tetrahedral graph), K3,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