{
  "id": "1311.5051",
  "version": "v2",
  "published": "2013-11-20T13:44:14.000Z",
  "updated": "2016-09-06T13:27:58.000Z",
  "title": "Separating path systems",
  "authors": [
    "Victor Falgas-Ravry",
    "Teeradej Kittipassorn",
    "Dániel Korándi",
    "Shoham Letzter",
    "Bhargav Narayanan"
  ],
  "comment": "21 pages, fixed misprints, Journal of Combinatorics",
  "categories": [
    "math.CO"
  ],
  "abstract": "We study separating systems of the edges of a graph where each member of the separating system is a path. We conjecture that every $n$-vertex graph admits a separating path system of size $O(n)$ and prove this in certain interesting special cases. In particular, we establish this conjecture for random graphs and graphs with linear minimum degree. We also obtain tight bounds on the size of a minimal separating path system in the case of trees.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-11-20T13:44:14.000Z",
      "abstract": "We study separating systems of the edges of a graph where each member of the separating system is a path. We conjecture that every graph on n vertices admits a separating path system of size linear in n and prove this in certain interesting special cases. In particular, we establish this conjecture for random graphs and graphs with linear minimum degree. We also obtain tight bounds on the size of a minimal separating path system in the case of trees.",
      "comment": "17 pages, 2 figure, includes an Appendix",
      "journal": null,
      "doi": null,
      "authors": [
        "Victor Falgas-Ravry",
        "Teeradej Kittipassorn",
        "Dániel Korándi",
        "Shoham Letzter",
        "Bhargav P. Narayanan"
      ]
    },
    {
      "version": "v2",
      "updated": "2016-09-06T13:27:58.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05C35",
      "05C70",
      "G.2.2",
      "05C38",
      "05C80"
    ],
    "keywords": [
      "linear minimum degree",
      "minimal separating path system",
      "random graphs",
      "study separating systems",
      "interesting special cases"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 21,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1311.5051F"
    }
  }
}