Highly connected non-2-linked digraphs

DOI10.1007/BF01275674MaRDI QIDQ1181017zbMATH OpenOpenAlexFDO

Authors Carsten Thomassen

Publication date 27 June 1992

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01275674

zbMATH Keywords

pathsdirected graphs

Mathematics Subject Classification ID

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

Recommendations

• Improved results on linkage problems
• An improved linear connectivity bound for tournaments to be highly linked
• Highly linked graphs
• k-linked and k-cyclic digraphs

Cites work

• 2-linked graphs
• Cycles in digraphs– a survey
• The directed subgraph homeomorphism problem

Cited in

(37)

• A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps.
• Lexicographic orientation algorithms
• Algorithms for finding a maximum non-\(k\)-linked graph
• Half-integral linkages in highly connected directed graphs
• Every (13k - 6)-strong tournament with minimum out-degree at least 28k - 13 is k-linked
• A minimum degree condition forcing a digraph to be k-linked
• Cycles through \(k\) vertices in bipartite tournaments
• On the structure of locally semicomplete digraphs
• Linkedness and Ordered Cycles in Digraphs
• Strong subgraph connectivity of digraphs
• Highly linked tournaments
• Constant congestion linkages in polynomially strong digraphs in polynomial time
• Disjoint paths in decomposable digraphs
• Finding a subdivision of a digraph
• Arc-disjoint directed and undirected cycles in digraphs
• A relaxation of the directed disjoint paths problem: a global congestion metric helps
• Counterexamples to the linkage conjecture for tournaments
• On the 2‐cyclic property in 2‐regular digraphs
• High connectivity keeping sets in graphs and digraphs
• New Menger-like dualities in digraphs and applications to half-integral linkages
• A new connectivity bound for a tournament to be highly linked
• On the k-linkage problem for generalizations of semicomplete digraphs
• (2k+1)-connected tournaments with large minimum out-degree are k-linked
• Algorithms for finding a maximum non-k-linked graph
• On \(k\)-strong and \(k\)-cyclic digraphs
• Balanced branchings in digraphs
• On 1-factors with prescribed lengths in tournaments
• Highly linked tournaments with large minimum out-degree
• Cycle-connected mixed graphs and related problems
• Cycle-connected mixed graphs and related problems
• Degree conditions for \(H\)-linked digraphs
• Oriented cycles in digraphs of large outdegree
• Improved results on linkage problems
• Disjoint sub(di)graphs in digraphs
• scientific article; zbMATH DE number 3972885 (Why is no real title available?)
• An improved linear connectivity bound for tournaments to be highly linked
• Highly linked graphs

This page was built for publication: Highly connected non-2-linked digraphs

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