Dan Cranston

*A New Lower Bound on the Density of Vertex Identifying Codes for the Infinite Hexagonal Grid*

**Abstract**. Given a graph *G*, an identifying code *C* ⊆ V(*G*) is a vertex set such that for any two distinct vertices
v_{1},v_{2} ∈ V(*G*), the sets N[*v*_{1}] ∩ *C* and N[*v*_{2}] ∩ *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.

.