The average connectivity of a digraph (Q1827842)

In the papers of \textit{L. W. Beineke, O. R. Oellermann} and \textit{R. E. Pippert} [Discrete Math. 252, 31-45 (2002; Zbl 1002.05040)] and \textit{P. Dankelmann} and \textit{O. R. Oellermann} [Discrete Appl. Math. 129, 305-318 (2003; Zbl 1021.05062)] the concept of average connectivity in a graph has been studied. In this paper this concept is considered in digraphs. For two distinct vertices \(u\) and \(v\) of a digraph \(D\), let \(\kappa_D(u,v)\) denote the connectivity from \(u\) to \(v\), the maximum number of internally disjoint directed paths from \(u\) to \(v\) in \(D\). Thus the connectivity \(\kappa(D)=\min\{\kappa_D(u,v)\mid u,v\in V(D)\}\). The average connectivity of \(D\), \(\overline{\kappa}(D)\), is the average connectivity from \(u\) to \(v\) over all ordered pairs \((u,v)\) of distinct vertices of \(D\). Sharp bounds are given on \(\overline{\kappa}(D)\) of orientations \(D\) of graphs in terms of their orders and sizes. These results are improved further for complete graphs (giving tournaments) and trees. It is proved that \(\overline{\kappa}_{\max}(T)\), the maximum average connectivity among all orientations of a tree \(T\), lies in the interval (2/9, 1/2] and a polynomial time procedure for finding \(\overline{\kappa}_{\max}(T)\) is suggested. The authors note that their results hold also for the average arc-connectivity of a digraph (defined as expected).