Digraphs without directed path of length two or three (Q1068100): Difference between revisions

The authors give characterizations of those digraphs which do not contain a directed path of length two (Theorem 1) and those digraphs which do not contain a directed path of length three (Theorem 2). The authors state a general conjecture (which appeared previously in a paper by Bermond, Germa, Heydemann and Sotteau) on the existence of a directed path of length k in a digraph with a sufficient number of arcs. The results of this paper show that the conjecture is true for \(k=2\) and \(k=3\).