Digraphs without directed path of length two or three

DOI10.1016/0012-365X(86)90193-7MaRDI QIDQ1068100zbMATH OpenOpenAlexFDO

Authors D. Sotteau, Adam Paweł Wojda

Publication date 1986

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0012-365x(86)90193-7

zbMATH Keywords

digraphsdirected path

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38)

Review text

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\).

Recommendations

• scientific article; zbMATH DE number 4004210
• On digraphs with no two disjoint directed cycles
• Directed graphs without short cycles
• On diregular digraphs with degree two and excess three
• scientific article; zbMATH DE number 3943846
• Disjoint directed and undirected paths and cycles in digraphs
• Digraphs that have at most one walk of a given length with the same endpoints
• Directed triangles in digraphs
• Graphs without cycles of even length
• scientific article; zbMATH DE number 3887733

Cites work

• Chemins Et Circuits Dans Les Graphes Orientes
• Digraphs without directed path of length two or three

Cited in

(7)

• Digraphs without directed path of length two or three
• Structural properties of directed \(P_2\)-path graphs
• scientific article; zbMATH DE number 3891406 (Why is no real title available?)
• scientific article; zbMATH DE number 4004210 (Why is no real title available?)
• Antipaths in oriented graphs
• A note concerning paths and independence number in digraphs
• Counting paths in digraphs

This page was built for publication: Digraphs without directed path of length two or three

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