- Distance-regular graph
-
Graph families defined by their automorphisms distance-transitive distance-regular strongly regular symmetric (arc-transitive) t-transitive, t ≥ 2 (if connected)
vertex- and edge-transitive edge-transitive and regular edge-transitive vertex-transitive regular Cayley graph skew-symmetric asymmetric In mathematics, a distance-regular graph is a regular graph such that for any two vertices v and w at distance i the number of vertices adjacent to w and at distance j from v is the same. 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.
Alternatively, a distance-regular graph is a graph for which there exist integers bi,ci,i=0,...,d such that for any two vertices x,y in G and distance i=d(x,y), there are exactly ci neighbors of y in Gi-1(x) and bi neighbors of y in Gi+1(x), where Gi(x) is the set of vertices y of G with d(x,y)=i (Brouwer et al. 1989, p. 434). The array of integers characterizing a distance-regular graph is known as its intersection array.
A distance-regular graph with diameter 2 is strongly regular, and conversely (unless the graph is disconnected).
Contents
Intersection numbers
It is usual to use the following notation for a distance-regular graph G. The number of vertices is n. The number of neighbors of w (that is, vertices adjacent to w) whose distance from v is i, i + 1, and i − 1 is denoted by ai, bi, and ci, respectively; these are the intersection numbers of G. Obviously, a0 = 0, c0 = 0, and b0 equals k, the degree of any vertex. If G has finite diameter, then d denotes the diameter and we have bd = 0. Also we have that ai+bi+ci= k
The numbers ai, bi, and ci are often displayed in a three-line array
called the intersection array of G. They may also be formed into a tridiagonal matrix
called the intersection matrix.
Distance adjacency matrices
Suppose G is a connected distance-regular graph. For each distance i = 1, ..., d, we can form a graph Gi in which vertices are adjacent if their distance in G equals i. Let Ai be the adjacency matrix of Gi. For instance, A1 is the adjacency matrix A of G. Also, let A0 = I, the identity matrix. This gives us d + 1 matrices A0, A1, ..., Ad, called the distance matrices of G. Their sum is the matrix J in which every entry is 1. There is an important product formula:
- AAi = aiAi + biAi + 1 + ciAi − 1.
From this formula it follows that each Ai is a polynomial function of A, of degree i, and that A satisfies a polynomial of degree d + 1. Furthermore, A has exactly d + 1 distinct eigenvalues, namely the eigenvalues of the intersection matrix B,of which the largest is k, the degree.
The distance matrices span a vector subspace of the vector space of all n × n real matrices. It is a remarkable fact that the product Ai Aj of any two distance matrices is a linear combination of the distance matrices:
This means that the distance matrices generate an association scheme. The theory of association schemes is central to the study of distance-regular graphs. For instance, the fact that Ai is a polynomial function of A is a fact about association schemes.
Examples
- Complete graphs are distance-regular with diameter 1 and degree v−1.
- Cycles C2d+1 of odd length are distance-regular with k = 2 and diameter d. The intersection numbers ai = 0, bi = 1, and ci = 1, except for the usual special cases (see above) and cd = 2.
- All Moore graphs, in particular the Petersen graph and the Hoffman-Singleton graph, are distance-regular.
- Strongly regular graphs are distance-regular.
- The odd graphs are distance-regular.
Notes
References
- A.E. Brouwer, A.M. Cohen, and A. Neumaier (1989), Distance Regular Graphs. Berlin, New York: Springer-Verlag. ISBN 3-540-50619-5, ISBN 0-387-50619-5
- Godsil, C. D. (1993). Algebraic combinatorics. Chapman and Hall Mathematics Series. New York: Chapman and Hall. pp. xvi+362. ISBN 0-412-04131-6. MR1220704.
Categories:- Algebraic graph theory
- Graph families
- Regular graphs
Wikimedia Foundation. 2010.