Minimum average distance of strong orientations of graphs Original Research Article

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 μ→min(G) is the minimum average distance taken over all strong orientations of G. A lower bound for μ→min(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 μ→min(G) in terms of μ(G). However, if every edge of G lies on 3-cycle, then it is shown that μ→min(G)⩽74μ(G). This bound is improved for maximal planar graphs to 53μ(G) and even further to 32μ(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.