Solving a Conjecture on Identification in Hamming Graphs

Authors Ville Junnila, Tero Laihonen, Tuomo Lehtilä

Publication date 4 May 2018

Orthogonal arrays, Latin squares, Room squares (05B15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Linear codes (general theory) (94B05) Combinatorial codes (94B25) Bounds on codes (94B65)

Abstract: Identifying codes in graphs have been widely studied since their introduction by Karpovsky, Chakrabarty and Levitin in 1998. In particular, there are a lot of 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 general Hamming graphs

K_{q}^{n}

. They stated, for instance, that

g a m m a^{I D} (K_{q}^{n}) l e q q^{n - 1}

for any

q

and

n g e q 3

. Moreover, they conjectured that

g a m m a^{I D} (K_{q}^{3}) = q^{2}

. In this article, we show that

g a m m a^{I D} (K_{q}^{3}) l e q q^{2} - q / 4

when

q

is a power of four, disproving the conjecture. Our approach is based on the recursive use of suitable designs. Goddard and Wash also gave the following lower bound

g a m m a^{I D} (K_{q}^{3}) g e q^{2} - q s q r t q

. We improve this bound to

g a m m a^{I D} (K_{q}^{3}) g e q^{2} - f r a c 32 q

. The conventional methods used for obtaining lower bounds on identifying codes do not help here. Hence, we provide a different technique building on the approach of Goddard and Wash. Moreover, we improve the above mentioned bound

g a m m a^{I D} (K_{q}^{n}) l e q q^{n - 1}

to

g a m m a^{I D} (K_{q}^{n}) l e q q^{n - k}

for

n = 3 f r a c q^{k} - 1 q - 1

when

q

is a prime power. For this bound, we utilize suitable linear codes over finite fields and a class of closely related codes, namely, the self-locating-dominating codes. In addition, we show that the self-locating-dominating codes satisfy the result

g a m m a^{S L D} (K_{q}^{3}) = q^{2}

related to the above conjecture.

This page was built for publication: Solving a Conjecture on Identification in Hamming Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6301164)