Distance-regular graph
This article needs additional citations for verification. (June 2009) (Learn how and when to remove this template message) |
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.
Contents
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 distance-regular graph 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 .
Algebraic properties
- for all .
- The adjacency algebra of is the Bose-Mesner algebra of an association scheme where pairs of vertices on are related by their distance; moreover, has distinct eigenvalues if it is connected.
Intersection matrices
There is a tridiagonal matrix , called the intersection matrix of , such that for any vertex on :
where .
The characteristic polynomial of is the minimal polynomial of .
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 connected distance-regular graphs of valency for all .^{[1]}
Cubic distance-regular graphs
The cubic distance-regular graphs have been completely classified.
The 13 distinct cubic distance-regular graphs are K_{4} (or tetrahedron), K_{3,3}, the Petersen graph, the cube, the Heawood graph, the Pappus graph, the Coxeter graph, the Tutte–Coxeter graph, the dodecahedron, 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. doi:10.1016/j.aim.2014.09.025.
Further reading
- Godsil, C. D. (1993). Algebraic combinatorics. Chapman and Hall Mathematics Series. New York: Chapman and Hall. pp. xvi+362. ISBN 0-412-04131-6. MR 1220704.