Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
419616 | Discrete Applied Mathematics | 2013 | 10 Pages |
Abstract
An rr-identifying code in a graph G=(V,E)G=(V,E) is a subset C⊆VC⊆V such that for each u∈Vu∈V the intersection of CC and the ball of radius rr centered at uu is nonempty and unique. Previously, rr-identifying codes have been studied in various grids. In particular, it has been shown that there exists a 22-identifying code in the square grid with density 5/29≈0.1725/29≈0.172 and that there are no 22-identifying codes with density smaller than 3/20=0.153/20=0.15. Recently, the lower bound has been improved to 6/37≈0.1626/37≈0.162 by Martin and Stanton (2010) [11]. In this paper, we further improve the lower bound by showing that there are no 22-identifying codes in the square grid with density smaller than 6/35≈0.1716/35≈0.171.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Ville Junnila,