In the mathematical field of graph theory, a distance-regular graph is a regular graph such that for any two verticesv and w, the number of vertices at distancej from v and at distance k from w depends only upon j, k, and the distance between v and w.
This article needs additional citations for verification. (June 2009)
Quick Facts Graph families defined by their automorphisms, → ...
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 in which is the diameter of the graph and for each , gives the number of neighbours of at distance from and gives the number of neighbours of at distance from for any pair of vertices and at distance . There is also the number that gives the number of neighbours of at distance from . The numbers are called the intersection numbers of the graph. They satisfy the equation where is the valency, i.e., the number of neighbours, of any vertex.
It turns out that a graph of diameter 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 is a connected distance-regular graph of valency with intersection array . For each let denote the number of vertices at distance from any given vertex and let denote the -regular graph with adjacency matrix formed by relating pairs of vertices on at distance .
Graph-theoretic properties
for all .
and .
Spectral properties
has distinct eigenvalues.
The only simple eigenvalue of is or both and if is bipartite.
for any eigenvalue multiplicity of unless is a complete multipartite graph.
for any eigenvalue multiplicity of unless is a cycle graph or a complete multipartite graph.
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).
Cubic distance-regular graphs
The cubic distance-regular graphs have been completely classified.