On a Conjecture Regarding Identification in Hamming Graphs

Source abstract

In 2013, Goddard and Wash studied identifying codes in the Hamming graphs $K_q^n$. They stated, for instance, that $\gamma^{ID}(K_q^n)\leqslant q^{n-1}$ for any $q$ and $n\geqslant 3$. Moreover, they conjectured that $\gamma^{ID}(K_q^3)=q^2$. In this article, we show that $\gamma^{ID}(K_q^3)\leqslant q^2-q/4$ when $q$ is a power of four, which disproves the conjecture. Goddard and Wash also gave the lower bound $\gamma^{ID}(K_q^3)\geqslant q^2-q\sqrt{q}$. We improve this bound to $\gamma^{ID}(K_q^3)\geqslant q^2-\frac{3}{2} q$. Moreover, we improve the above mentioned bound $\gamma^{ID}(K_q^n)\leqslant q^{n-1}$ to $\gamma^{ID}(K_q^n)\leqslant q^{n-k}$ for $n=3\frac{q^k-1}{q-1}$ and to $\gamma^{ID}(K_q^n)\leqslant 3q^{n-k}$ for $n=\frac{q^k-1}{q-1}$, when $q$ is a prime power. For these bounds, we utilize two classes of closely related codes, namely, the self-identifying and the self-locating-dominating codes. In addition, we show that the self-locating-dominating codes satisfy the result $\gamma^{SLD}(K_q^3)=q^2$ related to the above conjecture.