### 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 n^{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 4 n^{4} / 75 using Bondy's result for Thomassé's conjecture.

Original language | English (US) |
---|---|

Pages (from-to) | 961-975 |

Number of pages | 15 |

Journal | European Journal of Combinatorics |

Volume | 31 |

Issue number | 3 |

DOIs | |

State | Published - 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

Seymour, P., & Sullivan, B. D. (2010). Counting paths in digraphs.

*European Journal of Combinatorics*,*31*(3), 961-975. https://doi.org/10.1016/j.ejc.2009.05.008