This article needs additional citations for verification. (June 2009) |
Graph families defined by their automorphisms | ||||
---|---|---|---|---|
distance-transitive | → | distance-regular | ← | strongly regular |
↓ | ||||
symmetric (arc-transitive) | ← | t-transitive, t ≥ 2 | skew-symmetric | |
↓ | ||||
_{(if connected)} vertex- and edge-transitive |
→ | edge-transitive and regular | → | edge-transitive |
↓ | ↓ | ↓ | ||
vertex-transitive | → | regular | → | _{(if bipartite)} biregular |
↑ | ||||
Cayley graph | ← | zero-symmetric | asymmetric |
In mathematics, 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 i = d(v, w).
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
It turns out that a graph of diameter is distance-regular if and only if there is an array of integers such that for all , 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 on . The array of integers characterizing a distance-regular graph is known as its intersection array.
Cospectral distance-regular graphs
A pair of connected distance-regular graphs are cospectral if and only if they have 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 all : let denote the -regular graph with adjacency matrix formed by relating pairs of vertices on at distance , and let denote the number of neighbours of at distance from for any pair of vertices and at distance on .
Graph-theoretic properties
- for all .
- and .
Spectral properties
- 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 a simple eigenvalue of .
- has distinct eigenvalues.
If is strongly regular, then and .
Examples
Some first examples of distance-regular graphs include:
- The complete graphs.
- The cycles 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 K_{4} (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.
References
- ^ 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. arXiv:0909.5253. doi:10.1016/j.aim.2014.09.025. S2CID 18869283.
- ^ Godsil, C. D. (1988-12-01). "Bounding the diameter of distance-regular graphs". Combinatorica. 8 (4): 333–343. doi:10.1007/BF02189090. ISSN 0209-9683. S2CID 206813795.
Further reading
- Godsil, C. D. (1993). Algebraic combinatorics. Chapman and Hall Mathematics Series. New York: Chapman and Hall. pp. xvi+362. ISBN 978-0-412-04131-0. MR 1220704.