The 2-linkage problem for acyclic digraphs

DOI10.1016/S0012-365X(85)80022-4MaRDI QIDQ1057282zbMATH OpenOpenAlexFDO

Authors Carsten Thomassen

Publication date 1985

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(85)80022-4

zbMATH Keywords

acyclic digraphdirected pathsdistinct cyclesshortest cycles

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38)

Review text

The paper solves the problem of finding two disjoint directed paths with prescribed ends in an acyclic digraph. This is accomplished by reducing the problem to one of planarity test of an undirected graph. Necessary and sufficient conditions are given in terms of certain forbidden subdigraphs. As a result, it is shown that if any three cycles of a digraph have a common vertex, then all cycles have a common vertex. A precise structural characterization of digraphs of order n and girth \(g\geq 2n/3\) is given. From this it is shown that any such digraph has at most \(3^{n-g}\) distinct cycles and that a digraph of order n and girth \(g\geq 4\) has at most \(2^{n-g}\) shortest cycles.

Recommendations

• scientific article; zbMATH DE number 4085689
• On digraphs with no two disjoint directed cycles
• Disjoint paths in acyclic digraphs
• On the problem of finding disjoint cycles and dicycles in a digraph
• The directed 2-linkage problem with length constraints

Cites work

• 2-linked graphs
• Cycles in digraphs– a survey
• Disjoint cycles in digraphs
• Disjoint paths in graphs
• Efficient Planarity Testing
• scientific article; zbMATH DE number 3613081 (Why is no real title available?)
• scientific article; zbMATH DE number 3630786 (Why is no real title available?)
• scientific article; zbMATH DE number 3204690 (Why is no real title available?)
• On independent circuits of a digraph
• On the number of cycles possible in digraphs with large girth
• Planarity and duality of finite and infinite graphs
• The directed subgraph homeomorphism problem

Cited in

(22)

• Sign-nonsingular matrices and even cycles in directed graphs
• Characterization of even directed graphs
• On digraphs with no two disjoint directed cycles
• Finding a homotopy base for directed paths in an acyclic graph
• Linkages in locally semicomplete digraphs and quasi-transitive digraphs
• Disjoint paths in acyclic digraphs
• Nearly sign-nonsingular matrices
• Linear time algorithms for two disjoint paths problems on directed acyclic graphs
• On the problem of finding disjoint cycles and dicycles in a digraph
• DAG-width and circumference of digraphs
• Arc-disjoint directed and undirected cycles in digraphs
• Tournaments and Semicomplete Digraphs
• Existence of openly disjoint circuits through a vertex
• scientific article; zbMATH DE number 4085689 (Why is no real title available?)
• Vertex-disjoint directed and undirected cycles in general digraphs
• A note on short cycles in digraphs
• Thomassen's theorem on the two-linkage problem in acyclic digraphs: a shorter proof
• Oriented cycles in digraphs of large outdegree
• When all directed cycles have length three
• Openly disjoint circuits through a vertex in regular digraphs
• Hoàng-Reed conjecture holds for tournaments
• The Hoàng-Reed conjecture for \(\delta ^{+}=3\)

This page was built for publication: The 2-linkage problem for acyclic digraphs

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