1. Definitions

Introduction

Some text

Equitable partitions

A partition (V0, V1, ..., Vk-1) of the vertex set of a simple graph G=(V,E) is called an equitable partitions (regular partition, partition design, perfect coloring; the last notion also means the corresponding k-valued function on V) iff the edges joining any two distinct cells Vi, Vj form a biregular subgraph and every cell Vi induces a regular subgraph of G. The degrees of such subgraphs compose the quotient matrix (Si,j).

Completely regular codes

A set C of vertices of a simple graph is called completely regular (often, a completely regular code) with covering radius ρ if the distance partition of the vertex set with respect to C is equitable and has ρ+1 cells. If (Si,j) is the corresponding (tridiagonal) quotient matrix, then the 2ρ-tuple [b0,b1,...,bρ-1;c1,c2,...,cρ]=[S0,1, S1,2, ..., Sρ-1,ρ; S1,0, S2,1, ..., Sρ,ρ-1] is called the intersection array of the completely regular code.

Remark. A definition of the completely regular codes that is more or less similar to the definition given here was firstly suggested by A.Neumaier in [Neu92]. Originally, [Del73, 5.2.3], a completely regular code was defined as a set C of vertices with the following property: the multiset of distances from any fixed graph vertex X to the elements of C is uniquely defined by the distance from X to C (i.e., it does not depend on the choice of X among the vertices at the same distance from C). For the distance regular graphs, both definitions are equivalent.

Distance-regular graphs

A connected regular graph is called distance regular iff every bipartite subgraph generated by (as the parts) two different cocentered spheres is biregular. Equivalently, iff every singleton is a completely regular code. The intersection array does not depend on the choice of a vertex and is called the intersection array of the distance-regular graph.

Hamming graphs, hypercubes

The Hamming graph H(n,q) is the Cartesian product of n copies of the complete graph on n vertices. So, the vertices of H(n,q) are then the n-tuples with elements from a set Σ of cardinality q, two tuples being adjacent iff they differ in exactly one position. The binary Hamming graph H(n,2) is also referred to as the n-cube, or a hypercube.

References

[Del73] Delsarte, P. An Algebraic Approach to Association Schemes of Coding Theory. Philips Res. Rep. Supplement 10, 1973.

[Neu92] A. Neumaier. Completely regular codes. Discrete Mathematics 106-107, 1992, 353-360.