An optimal strongly identifying code in the infinite triangular grid

Iiro Honkala

The electronic journal of combinatorics, Tome 17 (2010)

Résumé

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$.

Détail

DOI : 10.37236/363

Classification : 05C69, 68R10
Mots-clés : graph, identifying code, triangular grid, density