On a conjecture regarding identification in Hamming graphs
type: Item
instance of: scholarly article
title: On a conjecture regarding identification in Hamming graphs
zbMATH Open document ID: 1418.94075
author: Ville Junnila
author: Tero Laihonen
author: Tuomo Lehtilä
published in: The Electronic Journal of Combinatorics
publication date: 2019-07-11T00:00:00Z
full work available at URL: v26i2p45
review text: Summary: In [J. Comb. Math. Comb. Comput. 85, 97--106 (2013; Zbl 1274.05408)], \textit{W. Goddard} and \textit{K. 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.
Mathematics Subject Classification ID: 94B05
Mathematics Subject Classification ID: 94B25
Mathematics Subject Classification ID: 94B65
Mathematics Subject Classification ID: 05B15
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 7079125
MaRDI profile type: Publication
cites work: Identifying Codes in Hereditary Classes of Graphs and VC-Dimension
cites work: Locating-dominating codes: bounds and extremal cardinalities
cites work: Q4342497
cites work: Q5298903
cites work: Identifying codes of Cartesian product of two cliques of the same size
cites work: Embedding Incomplete Latin Squares
cites work: Connected Identifying Codes
cites work: Identifying codes in vertex-transitive graphs and strongly regular graphs
cites work: Q4368728
cites work: On identifying codes in the Cartesian product of a path and a complete graph
cites work: On a new class of identifying codes in graphs
cites work: More results on the complexity of identifying problems in graphs
cites work: Minimum Number of Input Clues in Robust Information Retrieval
cites work: On regular and new types of codes for location-domination
cites work: On a new class of codes for identifying vertices in graphs
cites work: Q4230829
cites work: Q3684148
cites work: On minimum identifying codes in some Cartesian product graphs
cites work: Domination and location in acyclic graphs
cites work: Q3803159
description: scientific article; zbMATH DE number 7079125