On multifold perfect codes and some other completely regular codes in the Doob graphs and quaternary Hamming graphs

2023/12/12 by Bespalov, Evgeny
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2312.07109

Abstract

We consider the problem of existence of perfect 2-colorings in the Doob graphs D(m,n) and 4-ary Hamming graphs H(n,4). We characterize all parameters for which multifold 1-perfect code in D(m,n) exists. Also, we prove that for any pair (b,c) that satisfy standard conditions (Lloyd's and sphere-packing conditions) there is perfect (b,c)-coloring in Doob graphs and Hamming graphs if diameter of graph and n are sufficiently large (n not less than 0, 1 or 8 for some cases). Also we obtain some completely regular codes with covering radius 2.

Related

• On the non-existence of extended perfect codes and some perfect colorings
• On extended perfect codes
• On the existence of some completely regular codes in Hamming graphs
• Completely regular codes with covering radius 1 and the second eigenvalue in 3-dimensional Hamming graphs
• Completely regular codes in graphs covered by a Hamming graph