On a conjecture regarding identification in Hamming graphs (Q2001977)

Summary: In [J. Comb. Math. Comb. Comput. 85, 97--106 (2013; Zbl 1274.05408)], \textit{W. Goddard} and \textit{K. 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.