On the structure of edge-connectivity of a vertex subset in a graph

Tuesday 22 November 2005
Alek Vainshtein, University of Haifa

Let G=(V,E) be an undirected graph, S be a subset of its vertices. An S-cut is an edge-cut of G that divides S nontrivially. We suggest a graph structure that represents simultaneously all the minimum S-cuts and the partition of V by these cuts. For an adequate description of this structure we introduce a new type of graphs: locally orientable graphs, which generalize digraphs.

Based on joint work with Ye. Dinitz.