Abstract. Given a graph G, an identifying code C ⊆ V(G) is a vertex set such that for any two distinct vertices v1,v2 ∈ V(G), the sets N[v1] ∩ C and N[v2] ∩ C are distinct and nonempty (here N[v] denotes a vertex v and its neighbors). Vertex identifying codes can model fault diagnosis in a multiprocessor system.
We study the case when G is the infinite hexagonal grid H. Cohen et.al. constructed two identifying codes for H with density 3/7 and proved that any identifying code for H must have density at least 16/39 ≈ 0.410256. Both their upper and lower bounds were best known until now. Here we prove a lower bound of 12/29 ≈ 0.413793. This is joint work with Gexin Yu, of William & Mary.
.