Optimality of a 2-identifying code in the hexagonal grid
Résumé
An r-identifying code in a graph G = (V;E) is a subset C V such that for each u 2 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 hexagonal grid with density 4=19 and that there are no 2-identifying codes with density smaller than 2=11. Recently, the lower bound has been improved to 1=5 by Martin and Stanton (2010). In this paper, we prove that the 2-identifying code with density 4=19 is optimal, i.e. that there does not exist a 2-identifying code in the hexagonal grid with smaller density.
Origine : Fichiers produits par l'(les) auteur(s)
Loading...