4 - Distance-regular graphs

Summary

A critical family of association schemes arise from distance-regular graphs. A graph is distance regular if for any two vertices u and v at distance k in the graph, the number of vertices w that are at distance i from u and j from v depends only on k, and not on the vertices u and v.

Suppose X is a graph with diameter d. The ith distance graph X_i of X has the same vertex set as X, and two vertices are adjacent in X_i if and only if they are distance i in X. For any graph X, the adjacency matrices of the distance graphs of X are called the distance matrices. The distance matrices for any graph are linearly independent and sum to J − I. It has been left as an exercise to show that if X is a distance-regular graph, then the distance matrices form an association scheme. Such an association scheme is called metric; these are discussed in detail in Section 4.1.

Let X be a graph and S a subset of the vertices of X. Denote by S_i the set of vertices of X at distance i from S. The distance partition of X relative to S is the partition δ_S = { S₁, …, S_r } of V (X). We say that S is a completely regular subset of X if δ_S is an equitable partition. If X is a distance-regular graph, then for any x ∈ V (X) the set S = { x} is completely regular. Moreover, the quotient graphs of X with respect to each δ_{{ x}} are isomorphic. For any distance partition δ_S = { S₁, …, S_r } of X, vertices in S_i can only be adjacent to vertices in S_i−1, S_i and S_i+1.