# American Institute of Mathematical Sciences

February  2014, 8(1): 35-52. doi: 10.3934/amc.2014.8.35

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

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

Received  March 2012 Published  January 2014

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\%$.
Citation: Florent Foucaud, Tero Laihonen, Aline Parreau. An improved lower bound for $(1,\leq 2)$-identifying codes in the king grid. Advances in Mathematics of Communications, 2014, 8 (1) : 35-52. doi: 10.3934/amc.2014.8.35
##### 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.  Google Scholar [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.  Google Scholar [3] I. Charon, O. Hudry and A. Lobstein, Identifying codes with small radius in some infinite regular graphs, Electr. J. Combin., 9 (2002), R11.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [13] A. Lobstein, Watching systems, identifying, locating-dominating and discriminating codes in graphs: a bibliography,, available from , ().   Google Scholar [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.  Google Scholar [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.  Google Scholar

show all references

##### 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.  Google Scholar [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.  Google Scholar [3] I. Charon, O. Hudry and A. Lobstein, Identifying codes with small radius in some infinite regular graphs, Electr. J. Combin., 9 (2002), R11.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [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.  Google Scholar [13] A. Lobstein, Watching systems, identifying, locating-dominating and discriminating codes in graphs: a bibliography,, available from , ().   Google Scholar [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.  Google Scholar [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.  Google Scholar
 [1] Mikko Pelto. On $(r,\leq 2)$-locating-dominating codes in the infinite king grid. Advances in Mathematics of Communications, 2012, 6 (1) : 27-38. doi: 10.3934/amc.2012.6.27 [2] Cristóbal Camarero, Carmen Martínez, Ramón Beivide. Identifying codes of degree 4 Cayley graphs over Abelian groups. Advances in Mathematics of Communications, 2015, 9 (2) : 129-148. doi: 10.3934/amc.2015.9.129 [3] Jinchao Xu. The single-grid multilevel method and its applications. Inverse Problems & Imaging, 2013, 7 (3) : 987-1005. doi: 10.3934/ipi.2013.7.987 [4] Kaifang Liu, Lunji Song, Shan Zhao. A new over-penalized weak galerkin method. Part Ⅰ: Second-order elliptic problems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2411-2428. doi: 10.3934/dcdsb.2020184 [5] Lunji Song, Wenya Qi, Kaifang Liu, Qingxian Gu. A new over-penalized weak galerkin finite element method. Part Ⅱ: Elliptic interface problems. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2581-2598. doi: 10.3934/dcdsb.2020196 [6] Frédéric Sur, Michel Grédiac. Towards deconvolution to enhance the grid method for in-plane strain measurement. Inverse Problems & Imaging, 2014, 8 (1) : 259-291. doi: 10.3934/ipi.2014.8.259 [7] Li-Bin Liu, Ying Liang, Jian Zhang, Xiaobing Bao. A robust adaptive grid method for singularly perturbed Burger-Huxley equations. Electronic Research Archive, 2020, 28 (4) : 1439-1457. doi: 10.3934/era.2020076 [8] Zhenwei Zhang, Xue Li, Yuping Duan, Ke Yin, Xue-Cheng Tai. An efficient multi-grid method for TV minimization problems. Inverse Problems & Imaging, 2021, 15 (5) : 1199-1221. doi: 10.3934/ipi.2021034 [9] Ying Liu, Yanping Chen, Yunqing Huang, Yang Wang. Two-grid method for semiconductor device problem by mixed finite element method and characteristics finite element method. Electronic Research Archive, 2021, 29 (1) : 1859-1880. doi: 10.3934/era.2020095 [10] Leonid Pestov, Victoria Bolgova, Oksana Kazarina. Numerical recovering of a density by the BC-method. Inverse Problems & Imaging, 2010, 4 (4) : 703-712. doi: 10.3934/ipi.2010.4.703 [11] Emily McMillon, Allison Beemer, Christine A. Kelley. Extremal absorbing sets in low-density parity-check codes. Advances in Mathematics of Communications, 2021  doi: 10.3934/amc.2021003 [12] Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028 [13] Yun Chen, Jiasheng Huang, Si Li, Yao Lu, Yuesheng Xu. A content-adaptive unstructured grid based integral equation method with the TV regularization for SPECT reconstruction. Inverse Problems & Imaging, 2020, 14 (1) : 27-52. doi: 10.3934/ipi.2019062 [14] Jiaping Yu, Haibiao Zheng, Feng Shi, Ren Zhao. Two-grid finite element method for the stabilization of mixed Stokes-Darcy model. Discrete & Continuous Dynamical Systems - B, 2019, 24 (1) : 387-402. doi: 10.3934/dcdsb.2018109 [15] Cheng Wang. Convergence analysis of the numerical method for the primitive equations formulated in mean vorticity on a Cartesian grid. Discrete & Continuous Dynamical Systems - B, 2004, 4 (4) : 1143-1172. doi: 10.3934/dcdsb.2004.4.1143 [16] Hao Li, Hai Bi, Yidu Yang. The two-grid and multigrid discretizations of the $C^0$IPG method for biharmonic eigenvalue problem. Discrete & Continuous Dynamical Systems - B, 2020, 25 (5) : 1775-1789. doi: 10.3934/dcdsb.2020002 [17] Francisco Guillén-González, Mamadou Sy. Iterative method for mass diffusion model with density dependent viscosity. Discrete & Continuous Dynamical Systems - B, 2008, 10 (4) : 823-841. doi: 10.3934/dcdsb.2008.10.823 [18] Maria Laura Delle Monache, Paola Goatin. A front tracking method for a strongly coupled PDE-ODE system with moving density constraints in traffic flow. Discrete & Continuous Dynamical Systems - S, 2014, 7 (3) : 435-447. doi: 10.3934/dcdss.2014.7.435 [19] Alfredo Lorenzi, Eugenio Sinestrari. Identifying a BV-kernel in a hyperbolic integrodifferential equation. Discrete & Continuous Dynamical Systems, 2008, 21 (4) : 1199-1219. doi: 10.3934/dcds.2008.21.1199 [20] Youjun Deng, Hongyu Liu, Wing-Yan Tsui. Identifying varying magnetic anomalies using geomagnetic monitoring. Discrete & Continuous Dynamical Systems, 2020, 40 (11) : 6411-6440. doi: 10.3934/dcds.2020285

2020 Impact Factor: 0.935