Graph orientations with set connectivity requirements

In an undirected or a directed graph, the edge-connectivity between two disjoint vertex sets XX and YY is defined as the minimum number of edges or arcs that should be removed for disconnecting all vertices in YY from those in XX. This paper discusses how to construct a directed graph from a given undirected graph by orienting edges so as to preserve the edge-connectivity on pairs of vertex sets as much as possible. We present several bounds on the gap between the edge-connectivities in the undirected graph and in the obtained directed graphs, which extends the Nash-Williams’ strong orientation theorem.