Henning, Michael A.; Oellermann, Ortrud R. The average connectivity of a digraph. (English) Zbl 1047.05024 Discrete Appl. Math. 140, No. 1-3, 143-153 (2004). In the papers of L. W. Beineke, O. R. Oellermann and R. E. Pippert [Discrete Math. 252, 31-45 (2002; Zbl 1002.05040)] and P. Dankelmann and 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). Reviewer: Ján Plesník (Bratislava) Cited in 8 Documents MSC: 05C40 Connectivity 05C20 Directed graphs (digraphs), tournaments 05C05 Trees 68R10 Graph theory (including graph drawing) in computer science Keywords:average connectivity; oriented graphs; oriented trees; tournaments Citations:Zbl 1002.05040; Zbl 1021.05062 PDFBibTeX XMLCite \textit{M. A. Henning} and \textit{O. R. Oellermann}, Discrete Appl. Math. 140, No. 1--3, 143--153 (2004; Zbl 1047.05024) Full Text: DOI References: [1] Beineke, L. W.; Oellermann, O. R.; Pippert, R. E., On the Steiner median of a tree, Discrete Appl. Math., 68, 249-258 (1996) · Zbl 0858.05033 [2] Beineke, L. W.; Oellermann, O. R.; Pippert, R. E., The average connectivity of a graph, Discrete Math., 252, 31-45 (2002) · Zbl 1002.05040 [3] Chartrand, G.; Oellermann, O. R., Applied and Algorithmic Graph Theory (1993), McGraw-Hill: McGraw-Hill New York [4] Dankelmann, P.; Oellermann, O. R., Bounds on the average connectivity of a graph, Discrete Appl. Math., 129, 305-318 (2003) · Zbl 1021.05062 [5] G.H. Fricke, O.R. Oellermann, H.C. Swart, The edge-connectivity, average edge-connectivity and degree conditions, Technical Report, 1999.; G.H. Fricke, O.R. Oellermann, H.C. Swart, The edge-connectivity, average edge-connectivity and degree conditions, Technical Report, 1999. [6] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), Freeman: Freeman New York · Zbl 0411.68039 [7] Plesnik, J., The sum of all distances in a graph or digraph, J. Graph Theory, 8, 1-21 (1984) · Zbl 0552.05048 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.