Dijoin

From Egres Open
Jump to: navigation, search

In a directed graph, a dijoin is a set of arcs covering every directed cut. For a positive integer k, a k-dijoin is a set of arcs containing k edges from every directed cut. A fundamental theorem about dijoins is the Lucchesi-Younger theorem on the minimum size of a dijoin.

The following observation (see e.g. Frank, Sebő and Tardos [1]) gives a useful property of inclusionwise minimal dijoins.

Lemma. Let D be a weakly connected digraph without cut arcs. If F is an inclusionwise minimal dijoin, then by reorienting the arcs of F we obtain a strongly connected digraph.

References

  1. A. Frank, A. Sebő, É. Tardos, Covering directed and odd cuts, Mathematical Programming Studies 22 (1984) 99-112. Journal link, Author link.