A1 Refereed original research article in a scientific journal
On a Conjecture Regarding Identification in Hamming Graphs
Authors: Junnila V, Laihonen T, Lehtila T
Publisher: ELECTRONIC JOURNAL OF COMBINATORICS
Publication year: 2019
Journal: The Electronic Journal of Combinatorics
Journal name in source: ELECTRONIC JOURNAL OF COMBINATORICS
Journal acronym: ELECTRON J COMB
Article number: ARTN P2.45
Volume: 26
Issue: 2
Number of pages: 25
ISSN: 1077-8926
eISSN: 1077-8926
Web address : https://www.combinatorics.org/ojs/index.php/eljc/article/view/v26i2p45/7859
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.
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.
UTU Research Portal