The average distance of a graph (strong digraph) G, denoted by mu(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 mu(min)(G) is the minimum average distance taken over all strong orientations of G. A lower bound for mu(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 mu(min)(G) in terms of mu(G). However, if every edge of G lies on 3-cycle, then it is shown that mu(min)(G) less than or equal to 7/4mu(G). This bound is improved for maximal planar graphs to 5/3mu(G) and even further to 3/2mu(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. (C) 2004 Elsevier B.V. All rights reserved.
展开▼
