Counting paths in digraphs

Paul Seymour, Blair D. Sullivan

Research output: Contribution to journalArticle

1 Scopus citations

Abstract

Say a digraph is k-free if it has no directed cycles of length at most k, for k ∈ Z+. Thomassé 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 2 n3 / 25 such paths, and prove that for the class of circular interval digraphs, an upper bound of n3 / 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 4 n4 / 75 using Bondy's result for Thomassé's conjecture.

Original languageEnglish (US)
Pages (from-to)961-975
Number of pages15
JournalEuropean Journal of Combinatorics
Volume31
Issue number3
DOIs
StatePublished - Apr 1 2010

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics

Fingerprint Dive into the research topics of 'Counting paths in digraphs'. Together they form a unique fingerprint.

  • Cite this