In the mathematics of

directed graph In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs. Definition In formal terms, a directed graph is an ordered pa ...

s, Woodall's conjecture is an unproven relationship between dicuts and

dijoin In mathematics, a dijoin is a subset of the edges of a directed graph, with the property that contracting every edge in the dijoin produces a strongly connected graph. Equivalently, a dijoin is a subset of the edges that, for every dicut, inclu ...

s. It was posed by

Douglas Woodall Douglas Robert Woodall (born November 1943 in Stoke-on-Trent) is a British mathematician and psephologist. He studied mathematics at the University of Cambridge, and earned his Ph.D. at the University of Nottingham in 1969, his thesis being " ...

in 1976.

Statement

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. If the minimum number of edges in a dicut is

k

, then there can be at most

k

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

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).

Partial results

It is a folklore result that the theorem is true for directed graphs whose minimum dicut has two edges. Any instance of the problem can be reduced to a

directed acyclic graph In mathematics, particularly graph theory, and computer science, a directed acyclic graph (DAG) is a directed graph with no directed cycles. That is, it consists of vertices and edges (also called ''arcs''), with each edge directed from one ve ...

by taking the

condensation Condensation is the change of the state of matter from the gas phase into the liquid phase, and is the reverse of vaporization. The word most often refers to the water cycle. It can also be defined as the change in the state of water vapor to ...

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).

Related results

A fractional weighted version of the conjecture, posed by

Jack Edmonds Jack R. Edmonds (born April 5, 1934) is an American-born and educated computer scientist and mathematician who lived and worked in Canada for much of his life. He has made fundamental contributions to the fields of combinatorial optimization, pol ...

and Rick Giles, was refuted by

Alexander Schrijver Alexander (Lex) Schrijver (born 4 May 1948 in Amsterdam) is a Dutch mathematician and computer scientist, a professor of discrete mathematics and optimization at the University of Amsterdam and a fellow at the Centrum Wiskunde & Informatica in ...

. 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.

References

External links

* *{{citation, url=http://garden.irmacs.sfu.ca/?q=op/woodalls_conjecture, title=Woodall's conjecture, work=Open Problem Garden, date=April 5, 2007 Directed graphs