Subconstituents

Subconstituents are a concept in graph theory used to describe the layers of vertices at fixed distances from a chosen vertex. Given a simple graph G = (V,E) and a base vertex x in V, the distance d(u,x) is the length of the shortest path from u to x. For each nonnegative integer i, the i-th subconstituent of x is the set V_i = {u in V : d(u,x) = i}. The union of all V_i over i = 0 to the eccentricity e(x) (or the diameter D of G) equals V, and V_0 = {x}. The induced subgraph on V_i is sometimes called the i-th subconstituent graph or i-th neighborhood.

In distance-regular graphs, the subconstituents have a highly regular structure. For a vertex in V_i, the number of neighbors it has in V_{i-1} is c_i and in V_{i+1} is b_i; the number of neighbors in V_i is a_i, with c_i + a_i + b_i = k, where k is the common degree. The sequence {b_0,...,b_{D-1}; c_1,...,c_D} is the intersection array of the graph with respect to x and is independent of the choice of x in a distance-regular graph. The i-th subconstituent thus plays a central role in the analysis of the graph’s spectrum and in the theory of association schemes and the Terwilliger algebra.

Subconstituents are also used in more concrete terms to study specific graphs, such as cycles or grids, where the sizes and connections of the layers reflect the local geometry around the base vertex.