An Optimal Strongly Identifying Code in the Infinite Triangular Grid

Abstract

Assume that $G = (V, E)$ is an undirected graph, and $C \subseteq V$. For every ${\bf v} \in V$, we denote by $I({\bf v})$ the set of all elements of $C$ that are within distance one from ${\bf v}$. If the sets $I({\bf v})\setminus \{{\bf v}\}$ for ${\bf v}\in V$ are all nonempty, and, moreover, the sets $\{ I({\bf v}), I({\bf v}) \setminus \{ {\bf v}\}\}$ for ${\bf v} \in V$ are disjoint, then $C$ is called a strongly identifying code. The smallest possible density of a strongly identifying code in the infinite triangular grid is shown to be $6/19$.