The existence of perfect codes in Doob graphs
arXiv:1810.03772 · doi:10.1109/TIT.2019.2946612
Abstract
We solve the problem of existence of perfect codes in the Doob graph. It is shown that 1-perfect codes in the Doob graph D(m,n) exist if and only if 6m+3n+1 is a power of 2; that is, if the size of a 1-ball divides the number of vertices. Keywords: perfect codes, distance-regular graphs, Doob graphs, Eisenstein-Jacobi integers.
5 IEEE pages. V.2: accepted version; the introduction has been extended by a mini-survey