English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Identifying codes in graphs have been widely studied since their introductionby Karpovsky, Chakrabarty and Levitin in 1998. In particular, there are a lotof results regarding the binary hypercubes, that is, the Hamming graphs$K_2^n$. In 2008, Gravier et al. started investigating identification in$K_q^2$. Goddard and Wash, in 2013, studied identifying codes in the generalHamming graphs $K_q^n$. They stated, for instance, that $\gamma^{ID}(K_q^n)\leqq^{n-1}$ for any $q$ and $n\geq3$. Moreover, they conjectured that$\gamma^{ID}(K_q^3)=q^2$. In this article, we show that $\gamma^{ID}(K_q^3)\leqq^2-q/4$ when $q$ is a power of four, disproving the conjecture. Our approachis based on the recursive use of suitable designs. Goddard and Wash also gavethe following lower bound $\gamma^{ID}(K_q^3)\ge q^2-q\sqrt{q}$. We improvethis bound to $\gamma^{ID}(K_q^3)\ge q^2-\frac{3}{2} q$. The conventionalmethods used for obtaining lower bounds on identifying codes do not help here.Hence, we provide a different technique building on the approach of Goddard andWash. Moreover, we improve the above mentioned bound $\gamma^{ID}(K_q^n)\leqq^{n-1}$ to $\gamma^{ID}(K_q^n)\leq q^{n-k}$ for $n=3\frac{q^k-1}{q-1}$ when$q$ is a prime power. For this bound, we utilize suitable linear codes overfinite fields and a class of closely related codes, namely, theself-locating-dominating codes. In addition, we show that theself-locating-dominating codes satisfy the result $\gamma^{SLD}(K_q^3)=q^2$related to the above conjecture.

Solving a Conjecture on Identification in Hamming Graphs