{
  "id": "1006.3779",
  "version": "v1",
  "published": "2010-06-18T19:26:36.000Z",
  "updated": "2010-06-18T19:26:36.000Z",
  "title": "A New Lower Bound on the Density of Vertex Identifying Codes for the Infinite Hexagonal Grid",
  "authors": [
    "Daniel W. Cranston",
    "Gexin Yu"
  ],
  "comment": "16 pages, 10 figures",
  "journal": "Electronic J. of Combinatorics, R113, Volume 16(1), 2009",
  "categories": [
    "math.CO",
    "cs.DS"
  ],
  "abstract": "Given a graph $G$, an identifying code $C \\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 C$ and $N[v_2]\\cap C$ 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$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2010-06-18T19:26:36.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C35",
      "05C69",
      "05C90"
    ],
    "keywords": [
      "infinite hexagonal grid",
      "lower bound",
      "vertex identifying codes",
      "vertex set",
      "distinct vertices"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 16,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2010arXiv1006.3779C"
    }
  }
}