A "dijoin" in a digraph is a set of edges meeting every directed cut. D.R. Woodall conjectured in 1976 that if G is a digraph, and every directed cut of G has at least k edges, then there are k pairwise disjoint dijoins. This remains open, but a capacitated version is known to be false. In particular, A. Schrijver gave a digraph G and a subset S of its edge-set, such that every directed cut contains at least two edges in S, and yet there do not exist two disjoint dijoins included in S. In Schrijver's example, G is planar, and the subdigraph formed by the edges in S consists of three disjoint paths.We conjecture that when k= 2, the disconnectedness of S is crucial: more precisely, that if G is a digraph, and S⊆ E(G) forms a connected subdigr...
© 2021 The Authors. Journal of Graph Theory published by Wiley Periodicals LLCA dicut in a directed ...
AbstractWe show that the following problem is NP-complete: Given a digraph D and distinct vertices s...
AbstractIt is shown that there exists a positiveεso that for any integerk, every directed graph with...
A dijoin in a digraph is a set of edges meeting every directed cut. D. R. Woodall conjectured in 197...
A dicut in a directed graph is a cut for which all of its edges are directed to a common side of the...
A dicut in a directed graph is a cut for which all of its edges are directed to a common side of the...
An arborescence in a digraph is a tree directed away from its root.A classical theorem of Edmonds c...
An arborescence in a digraph is a tree directed away from its root. A classical theorem of Edmonds c...
A digraph H is infused in a digraph G if the vertices of H are mapped to vertices of G (not necessar...
A dicut in a directed graph is a cut for which all of its edges are directed to a common side of the...
An arborescence in a digraph is a tree directed away from its root. A classical theorem of Edmonds c...
AbstractLet c(x,y) denote the maximum number of edge-disjoint directed paths joining x to y in the d...
AbstractAs an extension of the disjoint paths problem, we introduce a new problem which we call the ...
We consider the problem of finding two disjoint directed paths with prescribed ends in an acylic dig...
We consider the problem of finding two disjoint directed paths with prescribed ends in an acylic dig...
© 2021 The Authors. Journal of Graph Theory published by Wiley Periodicals LLCA dicut in a directed ...
AbstractWe show that the following problem is NP-complete: Given a digraph D and distinct vertices s...
AbstractIt is shown that there exists a positiveεso that for any integerk, every directed graph with...
A dijoin in a digraph is a set of edges meeting every directed cut. D. R. Woodall conjectured in 197...
A dicut in a directed graph is a cut for which all of its edges are directed to a common side of the...
A dicut in a directed graph is a cut for which all of its edges are directed to a common side of the...
An arborescence in a digraph is a tree directed away from its root.A classical theorem of Edmonds c...
An arborescence in a digraph is a tree directed away from its root. A classical theorem of Edmonds c...
A digraph H is infused in a digraph G if the vertices of H are mapped to vertices of G (not necessar...
A dicut in a directed graph is a cut for which all of its edges are directed to a common side of the...
An arborescence in a digraph is a tree directed away from its root. A classical theorem of Edmonds c...
AbstractLet c(x,y) denote the maximum number of edge-disjoint directed paths joining x to y in the d...
AbstractAs an extension of the disjoint paths problem, we introduce a new problem which we call the ...
We consider the problem of finding two disjoint directed paths with prescribed ends in an acylic dig...
We consider the problem of finding two disjoint directed paths with prescribed ends in an acylic dig...
© 2021 The Authors. Journal of Graph Theory published by Wiley Periodicals LLCA dicut in a directed ...
AbstractWe show that the following problem is NP-complete: Given a digraph D and distinct vertices s...
AbstractIt is shown that there exists a positiveεso that for any integerk, every directed graph with...