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. 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. 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). 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). 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. 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. 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). Google Scholar

[8]

I. Honkala and T. Laihonen, Codes for identification in the king lattice,, Graphs Combin., 19 (2003), 505. 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. 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. 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. 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. 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. 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, (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. 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. 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). 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). 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. 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. 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). Google Scholar

[8]

I. Honkala and T. Laihonen, Codes for identification in the king lattice,, Graphs Combin., 19 (2003), 505. 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. 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. 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. 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. 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. 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, (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]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

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

[10]

Alfredo Lorenzi, Eugenio Sinestrari. Identifying a BV-kernel in a hyperbolic integrodifferential equation. Discrete & Continuous Dynamical Systems - A, 2008, 21 (4) : 1199-1219. doi: 10.3934/dcds.2008.21.1199

[11]

Lorenzo Audibert, Alexandre Girard, Houssem Haddar. Identifying defects in an unknown background using differential measurements. Inverse Problems & Imaging, 2015, 9 (3) : 625-643. doi: 10.3934/ipi.2015.9.625

[12]

Elena Beretta, Cecilia Cavaterra. Identifying a space dependent coefficient in a reaction-diffusion equation. Inverse Problems & Imaging, 2011, 5 (2) : 285-296. doi: 10.3934/ipi.2011.5.285

[13]

Dominique Duncan, Ronen Talmon, Hitten P. Zaveri, Ronald R. Coifman. Identifying preseizure state in intracranial EEG data using diffusion kernels. Mathematical Biosciences & Engineering, 2013, 10 (3) : 579-590. doi: 10.3934/mbe.2013.10.579

[14]

Giovanni Scardoni, Carlo Laudanna. Identifying critical traffic jam areas with node centralities interference and robustness. Networks & Heterogeneous Media, 2012, 7 (3) : 463-471. doi: 10.3934/nhm.2012.7.463

[15]

Maria Gabriella Mosquera, Vlado Keselj. Identifying electronic gaming machine gambling personae through unsupervised session classification. Big Data & Information Analytics, 2017, 2 (2) : 141-175. doi: 10.3934/bdia.2017015

[16]

Najla Mohammed, Peter Giesl. Grid refinement in the construction of Lyapunov functions using radial basis functions. Discrete & Continuous Dynamical Systems - B, 2015, 20 (8) : 2453-2476. doi: 10.3934/dcdsb.2015.20.2453

[17]

Chuong Van Nguyen, Phuong Huu Hoang, Hyo-Sung Ahn. Distributed optimization algorithms for game of power generation in smart grid. Numerical Algebra, Control & Optimization, 2019, 9 (3) : 327-348. doi: 10.3934/naco.2019022

[18]

Radu Balan, Peter G. Casazza, Christopher Heil and Zeph Landau. Density, overcompleteness, and localization of frames. Electronic Research Announcements, 2006, 12: 71-86.

[19]

Changguang Dong. On density of infinite subsets I. Discrete & Continuous Dynamical Systems - A, 2019, 39 (5) : 2343-2359. doi: 10.3934/dcds.2019099

[20]

Holly Gaff, Robyn Nadolny. Identifying requirements for the invasion of a tick species and tick-borne pathogen through TICKSIM. Mathematical Biosciences & Engineering, 2013, 10 (3) : 625-635. doi: 10.3934/mbe.2013.10.625

2018 Impact Factor: 0.879

Metrics

  • PDF downloads (5)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]