Highly connected non-2-linked digraphs
From MaRDI portal
A digraph \(D\) is said to be 2-linked if for any four vertices \(x_ 1\), \(x_ 2\), \(y_ 1\), and \(y_ 2\) there exist disjoint directed paths \(P_ 1\) and \(P_ 2\) starting at \(x_ 1\) and \(x_ 2\) and ending at \(y_ 1\) and \(y_ 2\), respectively. The author shows that for every positive integers \(k\) there exists a strongly \(k\)-connected digraph \(D\) that is not 2-linked.
Recommendations
Cited in
(38)- On the structure of locally semicomplete digraphs
- Cycles through \(k\) vertices in bipartite tournaments
- On \(k\)-strong and \(k\)-cyclic digraphs
- An improved linear connectivity bound for tournaments to be highly linked
- Strong subgraph connectivity of digraphs
- A relaxation of the directed disjoint paths problem: a global congestion metric helps
- (2k+1)-connected tournaments with large minimum out-degree are k-linked
- Every (13k - 6)-strong tournament with minimum out-degree at least 28k - 13 is k-linked
- On 1-factors with prescribed lengths in tournaments
- Highly linked tournaments with large minimum out-degree
- Balanced branchings in digraphs
- Highly linked graphs
- High connectivity keeping sets in graphs and digraphs
- Improved results on linkage problems
- Arc-disjoint directed and undirected cycles in digraphs
- Disjoint sub(di)graphs in digraphs
- Algorithms for finding a maximum non-k-linked graph
- Algorithms for finding a maximum non-\(k\)-linked graph
- Lexicographic orientation algorithms
- A minimum degree condition forcing a digraph to be k-linked
- Linkedness and Ordered Cycles in Digraphs
- scientific article; zbMATH DE number 3972885 (Why is no real title available?)
- Finding a subdivision of a digraph
- On the 2‐cyclic property in 2‐regular digraphs
- Highly linked tournaments
- A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps.
- Half-integral linkages in highly connected directed graphs
- Disjoint paths in decomposable digraphs
- Degree conditions for \(H\)-linked digraphs
- Cycle-connected mixed graphs and related problems
- Cycle-connected mixed graphs and related problems
- Counterexamples to the linkage conjecture for tournaments
- Constant congestion linkages in polynomially strong digraphs in polynomial time
- On the k-linkage problem for generalizations of semicomplete digraphs
- A new connectivity bound for a tournament to be highly linked
- New Menger-like dualities in digraphs and applications to half-integral linkages
- Oriented cycles in digraphs of large outdegree
- Revisiting directed disjoint paths on tournaments (and relatives)
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)
