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]

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

[2]

Agnaldo José Ferrari, Tatiana Miguel Rodrigues de Souza. Rotated $ A_n $-lattice codes of full diversity. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020118

[3]

Parikshit Upadhyaya, Elias Jarlebring, Emanuel H. Rubensson. A density matrix approach to the convergence of the self-consistent field iteration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 99-115. doi: 10.3934/naco.2020018

[4]

Wenbin Li, Jianliang Qian. Simultaneously recovering both domain and varying density in inverse gravimetry by efficient level-set methods. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020073

[5]

Mehdi Bastani, Davod Khojasteh Salkuyeh. On the GSOR iteration method for image restoration. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 27-43. doi: 10.3934/naco.2020013

[6]

Hong Niu, Zhijiang Feng, Qijin Xiao, Yajun Zhang. A PID control method based on optimal control strategy. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 117-126. doi: 10.3934/naco.2020019

[7]

Zexuan Liu, Zhiyuan Sun, Jerry Zhijian Yang. A numerical study of superconvergence of the discontinuous Galerkin method by patch reconstruction. Electronic Research Archive, 2020, 28 (4) : 1487-1501. doi: 10.3934/era.2020078

[8]

Yuxia Guo, Shaolong Peng. A direct method of moving planes for fully nonlinear nonlocal operators and applications. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020462

[9]

Noah Stevenson, Ian Tice. A truncated real interpolation method and characterizations of screened Sobolev spaces. Communications on Pure & Applied Analysis, 2020, 19 (12) : 5509-5566. doi: 10.3934/cpaa.2020250

[10]

Yue Feng, Yujie Liu, Ruishu Wang, Shangyou Zhang. A conforming discontinuous Galerkin finite element method on rectangular partitions. Electronic Research Archive, , () : -. doi: 10.3934/era.2020120

[11]

Gang Luo, Qingzhi Yang. The point-wise convergence of shifted symmetric higher order power method. Journal of Industrial & Management Optimization, 2021, 17 (1) : 357-368. doi: 10.3934/jimo.2019115

[12]

Leilei Wei, Yinnian He. A fully discrete local discontinuous Galerkin method with the generalized numerical flux to solve the tempered fractional reaction-diffusion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020319

[13]

Marion Darbas, Jérémy Heleine, Stephanie Lohrengel. Numerical resolution by the quasi-reversibility method of a data completion problem for Maxwell's equations. Inverse Problems & Imaging, 2020, 14 (6) : 1107-1133. doi: 10.3934/ipi.2020056

[14]

Gang Bao, Mingming Zhang, Bin Hu, Peijun Li. An adaptive finite element DtN method for the three-dimensional acoustic scattering problem. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020351

[15]

Abdollah Borhanifar, Maria Alessandra Ragusa, Sohrab Valizadeh. High-order numerical method for two-dimensional Riesz space fractional advection-dispersion equation. Discrete & Continuous Dynamical Systems - B, 2020  doi: 10.3934/dcdsb.2020355

[16]

Gervy Marie Angeles, Gilbert Peralta. Energy method for exponential stability of coupled one-dimensional hyperbolic PDE-ODE systems. Evolution Equations & Control Theory, 2020  doi: 10.3934/eect.2020108

[17]

Hassan Mohammad. A diagonal PRP-type projection method for convex constrained nonlinear monotone equations. Journal of Industrial & Management Optimization, 2021, 17 (1) : 101-116. doi: 10.3934/jimo.2019101

[18]

Jing Zhou, Cheng Lu, Ye Tian, Xiaoying Tang. A socp relaxation based branch-and-bound method for generalized trust-region subproblem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 151-168. doi: 10.3934/jimo.2019104

[19]

Zuliang Lu, Fei Huang, Xiankui Wu, Lin Li, Shang Liu. Convergence and quasi-optimality of $ L^2- $norms based an adaptive finite element method for nonlinear optimal control problems. Electronic Research Archive, 2020, 28 (4) : 1459-1486. doi: 10.3934/era.2020077

2019 Impact Factor: 0.734

Metrics

  • PDF downloads (40)
  • HTML views (0)
  • Cited by (2)

Other articles
by authors

[Back to Top]