New Bounds on the Minimum Density of a Vertex Identifying Code for the Infinite Hexagonal Grid

Abstract

For a graph, $G$, and a vertex $v\in V(G)$, let $N[v]$ be the set of vertices adjacent to and including $v$. A set $D\subseteq V(G)$ is a vertex identifying code if for any two distinct vertices $v_1,v_2\in V(G)$, the vertex sets $N[v_1]\cap D$ and $N[v_2]\cap D$ are distinct and non-empty. We consider the minimum density of a vertex identifying code for the infinite hexagonal grid. In 2000, Cohen et al. constructed two codes with a density of $3/7\approx 0.428571$, and this remains the best known upper bound. Until now, the best known lower bound was $12/29\approx 0.413793$ and was proved by Cranston and Yu in 2009. We present three new codes with a density of 3/7, and we improve the lower bound to $5/12\approx 0.416667$.

References in corpus (1)

• Improved Bounds for $r$-Identifying Codes of the Hex Grid