An improved lower bound for (1,<=2)-identifying codes in the king grid

Details An improved lower bound for (1,<=2)-identifying codes in the king grid An improved lower bound for (1,<=2)-identifying codes in the king grid

2011-11-10

arxiv.org/abs/1111.2477v1

Mathematics

Combinatorics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

An improved lower bound for (1,<=2)-identifying codes in the king grid does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An improved lower bound for (1,<=2)-identifying codes in the king grid, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An improved lower bound for (1,<=2)-identifying codes in the king grid will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-727881