Digraphs without directed path of length two or three (Q1068100)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Digraphs without directed path of length two or three |
scientific article |
Statements
Digraphs without directed path of length two or three (English)
0 references
1986
0 references
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\).
0 references
digraphs
0 references
directed path
0 references