Distance-regular graph
This article needs additional citations for verification. (June 2009) |
In the
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
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.
If is strongly regular, then and .
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 .
Classification of distance-regular graphs
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.
The 13 distinct cubic distance-regular graphs are
.References
Further reading
- MR 1220704.