DOE OSTI · 971587
Counting paths in digraphs
Abstract
Say a digraph is k-free if it has no directed cycles of length at most k, for k {element_of} Z{sup +}. 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 there are at most 2n{sup 3}/25 such paths, and prove that for the class of circular interval digraphs, an upper bound of n{sup 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{sup 4}/75 using Bondy's result for Thomasse's conjecture.
Explore related subjects
Keep this discovery
Explore connections, maps & timelines
Sullivan, Blair D, Seymour, Dr. Paul Douglas. 2010-01-01. Counting paths in digraphs. https://www.osti.gov/biblio/971587
Cite the original work for its findings. Save a collection to share your selection of sources.