Minimum average distance of strong orientations of graphs

The average distance of a graph (strong digraph) G, denoted by μ(G) is the average, among the distances between all pairs (ordered pairs) of vertices of G. If G is a 2-edge-connected graph, then μ→(G) is the minimum average distance taken over all strong orientations of G. A lower bound for μ→(G) in terms of the order, size, girth and average distance of G is established and shown to be sharp for several complete multipartite graphs. It is shown that there is no upper bound for μ→(G) in terms of μ(G). However, if every edge of G lies on 3-cycle, then it is shown that μ→(G) ≤ 7÷4μ(G). This bound is improved for maximal planar graphs to 5÷3μ(G) and even further to 5÷3μ(G) for eulerian maximal planar graphs and for outerplanar graphs with the property that every edge lies on 3-cycle. In the last case the bound is shown to be sharp.