Abstract: In Cayley graphs on the additive group of a small vector space over GF$(q)$, $q=2,3$, we look for completely regular (CR) codes whose parameters are new in Hamming graphs over the same field. The existence of a CR code in such a Cayley graph $G$ implies the existence of a CR code with the same parameters in the corresponding Hamming graph that covers $G$. In such a way, we find several completely regular codes with new parameters in Hamming graphs over GF$(2)$ and GF$(3)$. The most interesting findings are two new CR-$1$ (with covering radius~$1$) codes that are independent sets (such CR are equivalent to optimal orthogonal arrays attaining the Bierbrauer--Friedman bound) and one new CR-$2$ code. By recursive constructions, every new CR code induces an infinite sequence of CR codes (in particular, optimal orthogonal arrays if the original code is CR-$1$ and independent). Some of the found ternary CR codes disprove a conjectured generalization of the correlation-immunity bound on the strength of binary orthogonal arrays to the non-binary case. In between, we classify feasible parameters of CR codes in several strongly regular graphs.

Cite: Goryainov S. , Krotov D.
Completely regular codes in graphs covered by a Hamming graph
Designs, Codes and Cryptography. 2026. V.94. 213 :1-25. DOI: 10.1007/s10623-026-01955-2 Scopus OpenAlex

Dates:

Submitted:	Apr 30, 2026
Accepted:	Sep 21, 2026
Published print:	Oct 12, 2026
Published online:	Oct 12, 2026

Identifiers:

≡ Scopus:	2-s2.0-105053270721
≡ OpenAlex:	W4404451503

Altmetrics: