Minimum average distance of strong orientations of graphs (Q1887055)

The average distance of a graph or digraph \(G\) of order \(n\), denoted by \(\mu (G)\), is the average among the distances between all \(n(n-1)\) ordered pairs of vertices of \(G\) [see e.g. \textit{J. Plesník}, J. Graph Theory 8, 1--21 (1984; Zbl 0552.05048)]. If \(G\) is a 2-edge-connected graph, then \(\overrightarrow{\mu}_{\min }(G)\) is the minimum average distance taken over all strong orientations of \(G\). A sharp lower bound for \(\overrightarrow{\mu}_{\min }(G)\) is established in terms of the order, size, girth and \(\mu (G)\). In general, there is no upper bound for \(\overrightarrow{\mu}_{\min }(G)\) in terms of \(\mu (G)\). However, for some special classes of graphs such a bound is given.