An improved lower bound for $(1,\leq 2)$-identifying codes in the king grid

Florent Foucaud; Tero Laihonen; Aline Parreau

doi:10.3934/amc.2014.8.35

Article Contents

2014, Volume 8, Issue 1: 35-52. Doi: 10.3934/amc.2014.8.35

This issue Previous Article Special bent and near-bent functions Next Article Unified combinatorial constructions of optimal optical orthogonal codes

An improved lower bound for $(1,\leq 2)$-identifying codes in the king grid

1.
Department of Mathematics, University of Johannesburg, Auckland Park 2006
2.
Department of Mathematics and Statistics, University of Turku, 20014 Turku
3.
Institute of Mathematics, University of Liège, 4000 Liège

Received: March 2012

Published: February 2014

Abstract Related Papers Cited by

Abstract

We call a subset $C$ of vertices of a graph $G$ a $(1,\leq l)$-identifying code if for all subsets $X$ of vertices with size at most $\ell$, the sets $\{c\in C~|~\exists u\in X, d(u,c)\leq 1\}$ are distinct. The concept of identifying codes was introduced in 1998 by Karpovsky, Chakrabarty and Levitin. Identifying codes have been studied in various grids. In particular, it has been shown that there exists a $(1,\leq 2)$-identifying code in the king grid with density $\frac{3}{7}$ and that there are no such identifying codes with density smaller than $\frac{5}{12}$. Using a suitable frame and a discharging procedure, we improve the lower bound by showing that any $(1,\leq 2)$-identifying code of the king grid has density at least $\frac{47}{111}$. This reduces the gap between the best known lower and upper bounds on this problem by more than $56\%$.

Keywords:

Mathematics Subject Classification: Primary: 05C69; Secondary: 68P30.

Citation:

Related Papers

Cited by

References

[1]	Y. Ben-Haim and S. Litsyn, Exact minimum density of codes identifying vertices in the square grid, SIAM J. Discrete Math., 19 (2005), 69-82.doi: 10.1137/S0895480104444089.
[2]	I. Charon, I. Honkala, O. Hudry and A. Lobstein, The minimum density of an identifying code in the king lattice, Discrete Math., 276 (2004), 95-109.doi: 10.1016/S0012-365X(03)00306-6.
[3]	I. Charon, O. Hudry and A. Lobstein, Identifying codes with small radius in some infinite regular graphs, Electr. J. Combin., 9 (2002), R11.
[4]	G. Cohen, S. Gravier, I. Honkala, A. Lobstein, M. Mollard, C. Payan and G. Zémor, Improved identifying codes for the grid, Electr. J. Combin., 6 (1999), R19.
[5]	G. Cohen, I. Honkala, A. Lobstein and G. Zémor, Bounds for codes identifying vertices in the hexagonal grid, SIAM J. Discrete Math., 13 (2000), 492-504.doi: 10.1137/S0895480199360990.
[6]	G. Cohen, I. Honkala, A. Lobstein and G. Zémor, On codes identifying vertices in the two-dimensional square lattice with diagonals, IEEE Trans. Comp., 50 (2001), 174-176.doi: 10.1109/12.908992.
[7]	D. W. Cranston and G. Yu, A new lower bound on the density of vertex identifying codes for the infinite hexagonal grid, Electr. J. Combin., 16 (2009), R113.
[8]	I. Honkala and T. Laihonen, Codes for identification in the king lattice, Graphs Combin., 19 (2003), 505-516.doi: 10.1007/s00373-003-0531-2.
[9]	I. Honkala and T. Laihonen, On identifying codes in the triangular and square grids, SIAM J. Comput., 33 (2004), 304-312.doi: 10.1137/S0097539703433110.
[10]	I. Honkala and T. Laihonen, On identifying codes in the hexagonal mesh, Inform. Proc. Lett., 89 (2004), 9-14.doi: 10.1016/j.ipl.2003.09.009.
[11]	I. Honkala and T. Laihonen, On identification in the triangular grid, J. Combin. Theory Ser. B, 91 (2004), 67-86.doi: 10.1016/j.jctb.2003.10.002.
[12]	M. G. Karpovsky, K. Chakrabarty and L. B. Levitin, On a new class of codes for identifying vertices in graphs, IEEE Trans. Inform. Theory, 44 (1998), 599-611.doi: 10.1109/18.661507.
[13]	A. Lobstein, Watching systems, identifying, locating-dominating and discriminating codes in graphs: a bibliography, available from http://perso.enst.fr/~lobstein/bibLOCDOMetID.html
[14]	M. Pelto, New bounds for $(r,\le 2)$-identifying codes in the infinite king grid, Crypt. Commun., 2 (2010), 41-47.doi: 10.1007/s12095-009-0015-1.
[15]	S. Ray, R. Ungrangsi, F. De Pellegrini, A. Trachtenberg and D. Starobinski, Robust location detection in emergency sensor networks, in Proc. IEEE INFOCOM 2003, San Francisco, March 2003.doi: 10.1109/INFCOM.2003.1208941.