{
  "id": "1905.05083",
  "version": "v1",
  "published": "2019-05-13T15:25:26.000Z",
  "updated": "2019-05-13T15:25:26.000Z",
  "title": "Identifying codes in line digraphs",
  "authors": [
    "C. Balbuena",
    "C. Dalfó",
    "B. Mart\\'\\{i}nez-Barona"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "Given an integer $\\ell\\ge 1$, a $(1,\\le \\ell)$-identifying code in a digraph is a dominating subset $C$ of vertices such that all distinct subsets of vertices of cardinality at most $\\ell$ have distinct closed in-neighbourhood within $C$. In this paper, we prove that every $k$-iterated line digraph of minimum in-degree at least 2 and $k\\geq2$, or minimum in-degree at least 3 and $k\\geq1$, admits a $(1,\\le \\ell)$-identifying code with $\\ell\\leq2$, and in any case it does not admit a $(1,\\le \\ell)$-identifying code for $\\ell\\geq3$. Moreover, we find that the identifying number of a line digraph is lower bounded by the size of the original digraph minus its order. Furthermore, this lower bound is attained for oriented graphs of minimum in-degree at least 2.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2019-05-13T15:25:26.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C69",
      "05C20"
    ],
    "keywords": [
      "identifying code",
      "minimum in-degree",
      "original digraph minus",
      "iterated line digraph",
      "distinct subsets"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}