distanceregular

Distance-regular graphs are a class of connected regular graphs distinguished by a high degree of uniformity in how vertices are arranged at each distance from a fixed reference vertex. For a chosen vertex x in a graph G, the vertices are partitioned into layers Γ0(x) = {x}, Γ1(x), …, ΓD(x), where D is the diameter of G. The graph is distance-regular if, for any i and any vertex y in Γi(x), the numbers of neighbors of y that lie in Γi−1(x), Γi(x), and Γi+1(x) depend only on i and not on the particular pair (x,y). These numbers are denoted c_i, a_i, and b_i, respectively, with a_i = k − b_i − c_i, where k is the common degree of the graph. The sequence (b0, b1, …, bD−1; c1, c2, …, cD) is called the intersection array of G.

Consequences of this structure include that the distance partition around any vertex is equitable, and the adjacency algebra of the graph is commutative and can be described by a Bose–Mesner algebra. Distance-regular graphs generalize strongly regular graphs; they are distance-regular with diameter D = 2.

Notable examples include cycles Cn, hypercubes Qd, Johnson graphs J(n,k), Hamming graphs H(d,q), the Petersen graph, and the dodecahedral graph. They arise in algebraic graph theory and are closely connected to association schemes and spectral theory.

Further reading often cites the foundational work Distance-regular graphs by Brouwer, Cohen, and Neumaier, which develops the theory of intersection arrays, eigenvalues, and related combinatorial structures.