Completely Regular Codes as Optimal Structures

We survey several results showing that optimal structures from different classes attaining a specific bound are described as completely regular codes with certain parameters. Examples of such structures are error-correcting codes, orthogonal arrays, edge cuts. We prove two new results of such kind.At first, we prove that in an arbitrary finite regular graph, an algebraic T-design attaining the generalized Bierbrauer– Friedman–Potapov lower bound on its size is a completely regular code. (An algebraic T -design is a set of vertices whose characteristic function is orthogonal to all eigenfunctions corresponding to the T largest non-main eigenvalues of the graph.)At second, we show that every diameter-perfect code is completely regular in a specially constructed graph. (A diameter-perfect code of is a minimum-distance-d code C attaining the code-anticode bound |C| • |A| ≤ |S|, where S is the finite ambient metric space with transitive group of isometries and A, an anticode, is a set of diameter less than d).