
arXiv: 1111.2477
We call a subset $C$ of vertices of a graph $G$ a $(1,\leq \ell)$-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 3/7 and that there are no such identifying codes with density smaller than 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 47/111.
FOS: Computer and information sciences, density, Discrete Mathematics (cs.DM), Other types of codes, ta111, identifying codes, king grid, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), discharging method, Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science), Computer Science - Discrete Mathematics
FOS: Computer and information sciences, density, Discrete Mathematics (cs.DM), Other types of codes, ta111, identifying codes, king grid, Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.), FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), discharging method, Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science), Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
