A dicut is a partition of the vertices into two subsets such that all edges that cross the partition do so in the same direction. A dijoin is a subset of edges that, when contracted, produces a strongly connected graph; equivalently, it is a subset of edges that includes at least one edge from each dicut.[2]
If the minimum number of edges in a dicut is , then there can be at most disjoint dijoins in the graph, because each one must include a different edge from the smallest dicut. Woodall's conjecture states that, in this case, it is always possible to find disjoint dijoins. That is, any directed graph the minimum number of edges in a dicut equals the maximum number of disjoint dijoins that can be found in the graph (a packing of dijoins).[2][1]
Partial resultsedit
It is a folklore result that the theorem is true for directed graphs whose minimum dicut has two edges.[2] Any instance of the problem can be reduced to a directed acyclic graph by taking the condensation of the instance, a graph formed by contracting each strongly connected component to a single vertex. Another class of graphs for which the theorem has been proven true are the directed acyclic graphs in which every source vertex (a vertex without incoming edges) has a path to every sink vertex (a vertex without outgoing edges).[3][4]
Related resultsedit
A fractional weighted version of the conjecture, posed by Jack Edmonds and Rick Giles, was refuted by Alexander Schrijver.[5][6][2] In the other direction, the Lucchesi–Younger theorem states that the minimum size of a dijoin equals the maximum number of disjoint dicuts that can be found in a given graph.[7][8]
Referencesedit
^ abWoodall, D. R. (1978), "Menger and König systems", in Alavi, Yousef; Lick, Don R. (eds.), Theory and applications of graphs (Proc. Internat. Conf., Western Mich. Univ., Kalamazoo, Mich., 1976), Lecture Notes in Mathematics, vol. 642, Berlin: Springer, pp. 620–635, doi:10.1007/BFb0070416, MR 0499529
^ abcdAbdi, Ahmad; Cornuéjols, Gérard; Zlatin, Michael (2022), On packing dijoins in digraphs and weighted digraphs, arXiv:2202.00392
^Schrijver, A. (1982), "Min-max relations for directed graphs", Bonn Workshop on Combinatorial Optimization (Bonn, 1980), Annals of Discrete Mathematics, vol. 16, North-Holland, pp. 261–280, MR 0686312
^Feofiloff, P.; Younger, D. H. (1987), "Directed cut transversal packing for source-sink connected graphs", Combinatorica, 7 (3): 255–263, doi:10.1007/BF02579302, MR 0918396
^Edmonds, Jack; Giles, Rick (1977), "A min-max relation for submodular functions on graphs", Studies in integer programming (Proc. Workshop, Bonn, 1975), Annals of Discrete Mathematics, vol. 1, North-Holland, Amsterdam, pp. 185–204, MR 0460169
^Schrijver, A. (1980), Bachem, Achim; Grötschel, Martin; Korte, Bernhard (eds.), "A counterexample to a conjecture of Edmonds and Giles" (PDF), Discrete Mathematics, 32 (2): 213–215, doi:10.1016/0012-365X(80)90057-6, MR 0592858
^Lovász, László (1976), "On two minimax theorems in graph", Journal of Combinatorial Theory, Series B, 21 (2): 96–103, doi:10.1016/0095-8956(76)90049-6, MR 0427138
^Lucchesi, C. L.; Younger, D. H. (1978), "A minimax theorem for directed graphs", Journal of the London Mathematical Society, Second Series, 17 (3): 369–374, doi:10.1112/jlms/s2-17.3.369, MR 0500618
External linksedit
Feofiloff, Paulo (November 30, 2005), Woodall’s conjecture on Packing Dijoins: a survey(PDF)
"Woodall's conjecture", Open Problem Garden, April 5, 2007
April 06, 2024
woodall, conjecture, unsolved, problem, mathematics, does, minimum, number, edges, dicut, directed, graph, always, equal, maximum, number, disjoint, dijoins, more, unsolved, problems, mathematics, mathematics, directed, graphs, unproven, relationship, between,. Unsolved problem in mathematics Does the minimum number of edges in a dicut of a directed graph always equal the maximum number of disjoint dijoins more unsolved problems in mathematics In the mathematics of directed graphs Woodall s conjecture is an unproven relationship between dicuts and dijoins It was posed by Douglas Woodall in 1976 1 Contents 1 Statement 2 Partial results 3 Related results 4 References 5 External linksStatement editA dicut is a partition of the vertices into two subsets such that all edges that cross the partition do so in the same direction A dijoin is a subset of edges that when contracted produces a strongly connected graph equivalently it is a subset of edges that includes at least one edge from each dicut 2 If the minimum number of edges in a dicut is k displaystyle k nbsp then there can be at most k displaystyle k nbsp disjoint dijoins in the graph because each one must include a different edge from the smallest dicut Woodall s conjecture states that in this case it is always possible to find k displaystyle k nbsp disjoint dijoins That is any directed graph the minimum number of edges in a dicut equals the maximum number of disjoint dijoins that can be found in the graph a packing of dijoins 2 1 Partial results editIt is a folklore result that the theorem is true for directed graphs whose minimum dicut has two edges 2 Any instance of the problem can be reduced to a directed acyclic graph by taking the condensation of the instance a graph formed by contracting each strongly connected component to a single vertex Another class of graphs for which the theorem has been proven true are the directed acyclic graphs in which every source vertex a vertex without incoming edges has a path to every sink vertex a vertex without outgoing edges 3 4 Related results editA fractional weighted version of the conjecture posed by Jack Edmonds and Rick Giles was refuted by Alexander Schrijver 5 6 2 In the other direction the Lucchesi Younger theorem states that the minimum size of a dijoin equals the maximum number of disjoint dicuts that can be found in a given graph 7 8 References edit a b Woodall D R 1978 Menger and Konig systems in Alavi Yousef Lick Don R eds Theory and applications of graphs Proc Internat Conf Western Mich Univ Kalamazoo Mich 1976 Lecture Notes in Mathematics vol 642 Berlin Springer pp 620 635 doi 10 1007 BFb0070416 MR 0499529 a b c d Abdi Ahmad Cornuejols Gerard Zlatin Michael 2022 On packing dijoins in digraphs and weighted digraphs arXiv 2202 00392 Schrijver A 1982 Min max relations for directed graphs Bonn Workshop on Combinatorial Optimization Bonn 1980 Annals of Discrete Mathematics vol 16 North Holland pp 261 280 MR 0686312 Feofiloff P Younger D H 1987 Directed cut transversal packing for source sink connected graphs Combinatorica 7 3 255 263 doi 10 1007 BF02579302 MR 0918396 Edmonds Jack Giles Rick 1977 A min max relation for submodular functions on graphs Studies in integer programming Proc Workshop Bonn 1975 Annals of Discrete Mathematics vol 1 North Holland Amsterdam pp 185 204 MR 0460169 Schrijver A 1980 Bachem Achim Grotschel Martin Korte Bernhard eds A counterexample to a conjecture of Edmonds and Giles PDF Discrete Mathematics 32 2 213 215 doi 10 1016 0012 365X 80 90057 6 MR 0592858 Lovasz Laszlo 1976 On two minimax theorems in graph Journal of Combinatorial Theory Series B 21 2 96 103 doi 10 1016 0095 8956 76 90049 6 MR 0427138 Lucchesi C L Younger D H 1978 A minimax theorem for directed graphs Journal of the London Mathematical Society Second Series 17 3 369 374 doi 10 1112 jlms s2 17 3 369 MR 0500618External links editFeofiloff Paulo November 30 2005 Woodall s conjecture on Packing Dijoins a survey PDF Woodall s conjecture Open Problem Garden April 5 2007 Retrieved from https en wikipedia org w index php title Woodall 27s conjecture amp oldid 1211248407, wikipedia, wiki, book, books, library,
