subconstituent

A subconstituent, in graph theory and related areas, refers to a part of a graph obtained by fixing a vertex and considering all vertices at a given distance from that vertex. Formally, let G = (V, E) be a connected graph and v ∈ V. For each nonnegative integer i, define Γ_i(v) = {u ∈ V : dist(v, u) = i}, where dist is the shortest-path distance. The induced subgraph on Γ_i(v) is called the i-th subconstituent of G with respect to v, sometimes written as G_i(v) or Γ_i(v). The sets Γ_i(v) form a distance partition of V, with Γ_0(v) = {v} and Γ_i(v) empty for i larger than the graph’s diameter.

In distance-regular graphs, the subconstituents have a highly regular structure. Each vertex in Γ_i(v) has exactly c_i neighbors in Γ_{i-1}(v) and exactly b_i neighbors in Γ_{i+1}(v), where the constants c_i and b_i are part of the graph’s intersection array, and a_i = deg(v) − b_i − c_i counts neighbors within Γ_i(v). This uniformity underpins many spectral and combinatorial properties of the graph and leads to the notion of the subconstituent algebra (also called the Terwilliger algebra) used to study eigenstructures relative to a fixed vertex.

Examples help illustrate the concept. In a cycle C_n, with a fixed vertex v, Γ_0(v) is {v}, Γ_1(v) is the two neighbors of v (which induce two isolated vertices), and Γ_2(v) forms an edge (for sufficiently large n). Subconstituents thus capture the distance-based layering of a graph from a reference vertex and are fundamental in the study of distance-regular graphs and association schemes.