Distance-regular graph

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.

The intersection array of a distance-regular graph is the array

is the diameter of the graph and for each

gives the number of neighbours of

for any pair of vertices

There is also the number

that gives the number of neighbours of

The numbers

are called the intersection numbers of the graph.

They satisfy the equation

is the valency, i.e., the number of neighbours, of any vertex.

It turns out that a graph

is distance regular if and only if it has an intersection array in the preceding sense.

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.

is a connected distance-regular graph of valency

with intersection array

denote the number of vertices at distance

-regular graph with adjacency matrix

formed by relating pairs of vertices on

is strongly regular, then

Some first examples of distance-regular graphs include: There are only finitely many distinct connected distance-regular graphs of any given valency

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

[2] (with the exception of the complete multipartite 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.