{
  "id": "1210.8424",
  "version": "v1",
  "published": "2012-10-31T18:10:25.000Z",
  "updated": "2012-10-31T18:10:25.000Z",
  "title": "Counting paths in digraphs",
  "authors": [
    "Paul Seymour",
    "Blair D. Sullivan"
  ],
  "journal": "European Journal of Combinatorics 31, 2010, 961-975",
  "doi": "10.1016/j.ejc.2009.05.008",
  "categories": [
    "math.CO"
  ],
  "abstract": "Say a digraph is k-free if it has no directed cycles of length at most k, for positive integers k. Thomasse conjectured that the number of induced 3-vertex directed paths in a simple 2-free digraph on n vertices is at most (n-1)n(n+1)/15. We present an unpublished result of Bondy proving that there are at most 2n^3/25 such paths, and prove that for the class of circular interval digraphs, an upper bound of n^3/16 holds. We also study the problem of bounding the number of (non-induced) 4-vertex paths in 3-free digraphs. We show an upper bound of 4n^4/75 using Bondy's result for Thomasse's conjecture.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2012-10-31T18:10:25.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "counting paths",
      "upper bound",
      "circular interval digraphs",
      "thomasses conjecture",
      "bondys result"
    ],
    "tags": [
      "journal article"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2012arXiv1210.8424S"
    }
  }
}