Counting paths in digraphs

DOI10.1016/J.EJC.2009.05.008MaRDI QIDQ966150zbMATH OpenOpenAlexFDO

Authors Paul Seymour, Blair D. Sullivan

Publication date 27 April 2010

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.8424

zbMATH Keywords

circular interval digraphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Enumeration in graph theory (05C30) Paths and cycles (05C38)

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.

Recommendations

• Digraphs without directed path of length two or three
• On Sullivan's conjecture on cycles in 4-free and 5-free digraphs
• scientific article; zbMATH DE number 4198025
• On the number of vertex-disjoint cycles in digraphs
• Digraphs with maximum number of paths and cycles

Cites work

• scientific article; zbMATH DE number 3630786 (Why is no real title available?)
• On directed triangles in digraphs

Cited in

(8)

• scientific article; zbMATH DE number 4198025 (Why is no real title available?)
• Increasing paths in countable graphs
• On the number of alternating paths in bipartite complete graphs
• Counting paths with Schur transitions
• scientific article; zbMATH DE number 3922696 (Why is no real title available?)
• Counting paths in graphs
• scientific article; zbMATH DE number 1868869 (Why is no real title available?)
• On computing the path number of a graph

This page was built for publication: Counting paths in digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q966150)