{
  "id": "1302.5503",
  "version": "v1",
  "published": "2013-02-22T07:33:57.000Z",
  "updated": "2013-02-22T07:33:57.000Z",
  "title": "Transversals of Longest Paths and Cycles",
  "authors": [
    "Dieter Rautenbach",
    "Jean-Sébastien Sereni"
  ],
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "Let G be a graph of order n. Let lpt(G) be the minimum cardinality of a set X of vertices of G such that X intersects every longest path of G and define lct(G) analogously for cycles instead of paths. We prove that lpt(G) \\leq ceiling(n/4-n^{2/3}/90), if G is connected, lct(G) \\leq ceiling(n/3-n^{2/3}/36), if G is 2-connected, and \\lpt(G) \\leq 3, if G is a connected circular arc graph. Our bound on lct(G) improves an earlier result of Thomassen and our bound for circular arc graphs relates to an earlier statement of Balister \\emph{et al.} the argument of which contains a gap. Furthermore, we prove upper bounds on lpt(G) for planar graphs and graphs of bounded tree-width.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2013-02-22T07:33:57.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "longest path",
      "transversals",
      "circular arc graphs relates",
      "connected circular arc graph",
      "earlier result"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2013arXiv1302.5503R"
    }
  }
}