2012/02/03 by Ville Junnila, Junnila, Ville, Tero Laihonen +1
Biochemistry, Genetics and Molecular Biology · Computer Science · Medicine · #Advanced biosensing and bioanalysis techniques #Combinatorics (math.CO) #Cooperative Communication and Network Coding #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #SARS-CoV-2 detection and testing
paper · pdf · doi:10.48550/arxiv.1202.0670
openalex publication_date 2012/02/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An r-identifying code in a graph G = (V,E) is a subset C ⊆ V such that for each u ∈ V the intersection of C and the ball of radius r centered at u is non-empty 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.