Advances in Mathematics of Communications (AMC)

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

Pages: 35 - 52, Volume 8, Issue 1, February 2014      doi:10.3934/amc.2014.8.35

       Abstract        References        Full Text (444.6K)       Related Articles       

Florent Foucaud - Department of Mathematics, University of Johannesburg, Auckland Park 2006, South Africa (email)
Tero Laihonen - Department of Mathematics and Statistics, University of Turku, 20014 Turku, Finland (email)
Aline Parreau - Institute of Mathematics, University of Liège, 4000 Liège, Belgium (email)

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:  Identifying codes, king grid, density, discharging method.
Mathematics Subject Classification:  Primary: 05C69; Secondary: 68P30.

Received: March 2012;      Available Online: January 2014.