A new lower bound on the density of vertex identifying codes for the infinite hexagonal grid (Q2380272)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A new lower bound on the density of vertex identifying codes for the infinite hexagonal grid |
scientific article |
Statements
A new lower bound on the density of vertex identifying codes for the infinite hexagonal grid (English)
0 references
26 March 2010
0 references
Summary: Given a graph \(G\), an identifying code \({\mathcal 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 D\) and \(N[v_2]\cap 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\approx 0.410256\). Both their upper and lower bounds were best known until now. Here we prove a lower bound of \(12/29\approx 0.413793\).
0 references