Article Contents
Article Contents

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

• 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\%$.
Mathematics Subject Classification: Primary: 05C69; Secondary: 68P30.

 Citation:

•  [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.