
doi: 10.37236/7828
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.
Bounds on codes, Combinatorial codes, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), ta111, Orthogonal arrays, Latin squares, Room squares, Linear codes (general theory)
Bounds on codes, Combinatorial codes, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), ta111, Orthogonal arrays, Latin squares, Room squares, Linear codes (general theory)
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
