Minimum Average Distance Of Strong Orientations

An oriented graph D of a graph G is obtained from G by assigning a direction to each edge of G; such an oriented graph is also called an orientation of G. An orientation D of G is strong if every two vertices in D are mutually reachable in D. The average distance μ(G) of G is defined to be the average among all distances between all pairs (ordered pairs if G is a digraph) of vertices of G. Let μ|→min(G) denote the minimum average distance taken over all strong orientations of a graph G. This paper deals with μ|→min(G). The main is organized to two parts. Part one aims at bounding the index μ|→min(G). We give a lower bound for general graphs and an upper bound for complete multipartite graphs and Cartesian product graphs, respectively. In particular, we improve the bound for some special Cartesian product graphs. Moreover, a new index μ^*min(G) is introduced which is shown to have a closed relation with μ|→min(G). Then we give a lower bound for μ|→min(G) in terms of μ^*min(G). Part two is to solve the optimal orientation for complete bipartite graphs. To this end, a generalization of Sperner's theorem is established. By using this generalized Sperner's theorem, we determine the exact value of μ|→min(K_P,q) by constructing an optimal orientation.