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)) <= q(n-1) for any q and n >= 3. Moreover, they conjectured that gamma(ID)(K-q(3)) = q(2). In this article, we show that gamma(ID)(K-q(3)) <= 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)) >= q(2) - q root q. We improve this bound to gamma(ID)(K-q(3)) >= q(2) - 3/2q. Moreover, we improve the above mentioned bound gamma(ID)(K-q(n)) <= q(n-1) to gamma(ID)(K-q(n)) <= q(n-k) for n = 3 q(k)-1/q-1 and to gamma(ID)(K-q(n)) <= 3q(n-k) for n = 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. |
Year | DOI | Venue |
---|---|---|
2019 | 10.37236/7828 | ELECTRONIC JOURNAL OF COMBINATORICS |
Keywords | Field | DocType |
Hamming graph,identifying code,linear codes over finite fields,Latin square,location-domination | Discrete mathematics,Combinatorics,Conjecture,Hamming graph,Mathematics | Journal |
Volume | Issue | ISSN |
26 | 2 | 1077-8926 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Ville Junnila | 1 | 43 | 10.51 |
Tero Laihonen | 2 | 363 | 39.39 |
Tuomo Lehtilä | 3 | 2 | 2.06 |