Strong Orientation - Related Types of Orientation

Related Types of Orientation

If an undirected graph has an Euler tour, an Eulerian orientation of the graph (an orientation for which every vertex has indegree equal to its outdegree) may be found by orienting the edges consistently around the tour. These orientations are automatically strong orientations.

A theorem of Nash-Williams (1960, 1969) states that every undirected graph G has a well-balanced orientation. This is an orientation with the property that, for every pair of vertices u and v in G, the number of pairwise edge-disjoint directed paths from u to v in the resulting directed graph is at least, where k is the maximum number of paths in a set of edge-disjoint undirected paths from u to v. Nash-Williams' orientations also have the property that they are as close as possible to being Eulerian orientations: at each vertex, the indegree and the outdegree are within one of each other. The existence of well-balanced orientations, together with Menger's theorem, immediately implies Robbins' theorem: by Menger's theorem, a 2-edge-connected graph has at least two edge-disjoint paths between every pair of vertices, from which it follows that any well-balanced orientation must be strongly connected. More generally this result implies that every 2k-edge-connected undirected graph can be oriented to form a k-edge-connected directed graph.

A totally cyclic orientation of a graph G is an orientation in which each edge belongs to a directed cycle. For connected graphs, this is the same thing as a strong orientation, but totally cyclic orientations may also be defined for disconnected graphs, and are the orientations in which each connected component of G becomes strongly connected. Robbins' theorem can be restated as saying that a graph has a totally cyclic orientation if and only if it does not have a bridge. Totally cyclic orientations are dual to acyclic orientations (orientations that turn G into a directed acyclic graph) in the sense that, if G is a planar graph, and orientations of G are transferred to orientations of the planar dual graph of G by turning each edge 90 degrees clockwise, then a totally cyclic orientation of G corresponds in this way to an acyclic orientation of the dual graph and vice versa. The number of different totally cyclic orientations of any graph G is T_G(0,2) where T_G is the Tutte polynomial of the graph, and dually the number of acyclic orientations is T_G(2,0). As a consequence, Robbins' theorem implies that the Tutte polynomial has a root at the point (0,2) if and only if the graph G has a bridge.