On perfect codes and related concepts (Q5931253)

The concept of diameter perfect codes, which is a natural generalization of perfect codes (codes attaining the sphere-packing or Hamming bound), is introduced. The motivation for this work comes from the ``code-anticode'' bound of Delsarte in distance regular graphs. This bound in conjunction with the recent complete solution of diametric problems in the Hamming graph \(H_q(n)\) and the Johnson graph \(J(n,k)\) gives a sharpening of the sphere-packing bound. This paper gives some necessary conditions for the existence of diameter perfect codes. In the Hamming graph, all diameter perfect codes over alphabets of prime power size are characterized. The problem of tiling the vertex set of \(J(n,k)\) with caps (and maximal anticodes) is examined. Examples of diameter perfect codes in \(J(n,k)\) are given along with necessary conditions. It is shown that MDS codes are perfect in \(H_q(n)\), as are the extended Hamming and extended Golay codes. Perfect codes are also diameter perfect. It is proven that there are no others. It is shown that the problem of existence of diameter perfect caps in \(J(n,k)\) can be reduced in all cases to the problem of tiling the vertex set \(V_k^n\) with caps. It is proven that there are no tilings of \(V_k^n\) with optimal anticodes which are not balls. Finally, some open problems are given.