A1 Refereed original research article in a scientific journal
New lower bound for 2-identifying code in the square grid
Authors: Junnila V
Publisher: ELSEVIER SCIENCE BV
Publication year: 2013
Journal: Discrete Applied Mathematics
Journal name in source: DISCRETE APPLIED MATHEMATICS
Journal acronym: DISCRETE APPL MATH
Number in series: 13-14
Volume: 161
Issue: 13-14
First page : 2042
Last page: 2051
Number of pages: 10
ISSN: 0166-218X
DOI: https://doi.org/10.1016/j.dam.2013.02.032
Abstract
An r-identifying code in a graph G = (V, E) is a subset C subset of V such that for each u is an element of V the intersection of C and the ball of radius r centered at u is nonempty and unique. Previously, r-identifying codes have been studied in various grids. In particular, it has been shown that there exists a 2-identifying code in the square grid with density 5/29 approximate to 0.172 and that there are no 2-identifying codes with density smaller than 3/20 = 0.15. Recently, the lower bound has been improved to 6/37 approximate to 0.162 by Martin and Stanton (2010) [11]. In this paper, we further improve the lower bound by showing that there are no 2-identifying codes in the square grid with density smaller than 6/35 approximate to 0.171. (C) 2013 Elsevier B.V. All rights reserved.
An r-identifying code in a graph G = (V, E) is a subset C subset of V such that for each u is an element of V the intersection of C and the ball of radius r centered at u is nonempty and unique. Previously, r-identifying codes have been studied in various grids. In particular, it has been shown that there exists a 2-identifying code in the square grid with density 5/29 approximate to 0.172 and that there are no 2-identifying codes with density smaller than 3/20 = 0.15. Recently, the lower bound has been improved to 6/37 approximate to 0.162 by Martin and Stanton (2010) [11]. In this paper, we further improve the lower bound by showing that there are no 2-identifying codes in the square grid with density smaller than 6/35 approximate to 0.171. (C) 2013 Elsevier B.V. All rights reserved.
UTU Research Portal