{
  "id": "1107.0207",
  "version": "v2",
  "published": "2011-07-01T12:18:42.000Z",
  "updated": "2012-09-21T11:45:27.000Z",
  "title": "Identifying codes in line graphs",
  "authors": [
    "Florent Foucaud",
    "Sylvain Gravier",
    "Reza Naserasr",
    "Aline Parreau",
    "Petru Valicov"
  ],
  "journal": "Journal of Graph Theory 73, 4 (2013) 425-448",
  "doi": "10.1002/jgt.21686",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "An identifying code of a graph is a subset of its vertices such that every vertex of the graph is uniquely identified by the set of its neighbours within the code. We study the edge-identifying code problem, i.e. the identifying code problem in line graphs. If $\\ID(G)$ denotes the size of a minimum identifying code of an identifiable graph $G$, we show that the usual bound $\\ID(G)\\ge \\lceil\\log_2(n+1)\\rceil$, where $n$ denotes the order of $G$, can be improved to $\\Theta(\\sqrt{n})$ in the class of line graphs. Moreover, this bound is tight. We also prove that the upper bound $\\ID(\\mathcal{L}(G))\\leq 2|V(G)|-5$, where $\\mathcal{L}(G)$ is the line graph of $G$, holds (with two exceptions). This implies that a conjecture of R. Klasing, A. Kosowski, A. Raspaud and the first author holds for a subclass of line graphs. Finally, we show that the edge-identifying code problem is NP-complete, even for the class of planar bipartite graphs of maximum degree~3 and arbitrarily large girth.",
  "revisions": [
    {
      "version": "v2",
      "updated": "2012-09-21T11:45:27.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "line graph",
      "edge-identifying code problem",
      "planar bipartite graphs",
      "first author holds",
      "upper bound"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2011arXiv1107.0207F"
    }
  }
}