Graphs Related to Codes

Let $$V = F_{q}^{n} $$ be the vector space of n-tuples with entries in the finite field F _q with q elements, and let C be a linear code in V (i.e., a linear subspace of V). We define the coset graph Γ(C) of C by taking as vertices the cosets of C in V, and joining two cosets when they have representatives that differ in one coordinate (i.e., have Hamming distance one). In some cases Γ(C) turns out to be distance-regular. In section 11.1 we study this phenomenon in a more general setting. Instead of the vector space V (that is, instead of the Hamming graph H(n,q)), we take an arbitrary distance-regular graph Γ, and instead of the partition of V into cosets of C, we take an arbitrary partition Π of Γ, Now there is an obvious concept of quotient graph Γ / Π generalizing that of coset graph, and Theorem 11.1.6 gives a sufficient condition for this quotient graph to be distance-regular. Section 11.1 is the outgrowth of earlier discussions with A.R. Calderbank.