A new lower bound on the density of vertex identifying codes for the infinite hexagonal grid

Daniel W. Cranston ; Gexin Yu

The electronic journal of combinatorics, Tome 16 (2009) no. 1

Résumé

Given a graph $G$, an identifying code ${\cal D}\subseteq V(G)$ is a vertex set such that for any two distinct vertices $v_1,v_2\in V(G)$, the sets $N[v_1]\cap{\cal D}$ and $N[v_2]\cap{\cal D}$ are distinct and nonempty (here $N[v]$ denotes a vertex $v$ and its neighbors). 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\approx0.410256$. Both their upper and lower bounds were best known until now. Here we prove a lower bound of $12/29\approx0.413793$.

Détail

DOI : 10.37236/202

Classification : 05C35, 05C69, 05C90