Henning, Michael A.; Oellermann, Ortrud R. The average connectivity of regular multipartite tournaments. (English) Zbl 0977.05072 Australas. J. Comb. 23, 101-113 (2001). For a graph \(G\) with vertex set \(V\) and orientation \(D\) of its edge-set, let \(K(D)=\sum\kappa(u,v)\) where \(\kappa(u,v)\) denotes the number of internally disjoint directed \(uv\)-paths and summation is over \((V\times V)\text{diag}(V)\). The average connectivity of \(D\) is \(\overline{\kappa}(D)=K(D)/[p(p-1)]\). This graph parameter is computable in polynomial time, but determining its maximum and minimum values over all orientations \(D\) of \(G\) appears to be difficult. The present paper limits its consideration to complete multipartite graphs \(K_{n_1,\ldots,n_k}\). For such graphs, for \(\max_D\{\overline{\kappa}(D)\}\) an upper bound is found and an exact value is determined when \(n_1=\cdots=n_k\). An exact value of \(\min_D\{\overline{\kappa}(D)\}\) is determined when \(D\) is restricted to orientations such that if \(V_1,\ldots,V_k\) are the parts of \(G\) and if \(1\leq i<j\leq k\), then all the arcs between \(V_i\) and \(V_j\) are directed from \(V_i\) to \(V_j\). Reviewer: Mark E.Watkins (Syracuse) Cited in 2 Documents MSC: 05C40 Connectivity 05C20 Directed graphs (digraphs), tournaments Keywords:internally disjoint paths; complete multipartite graph; average connectivity PDFBibTeX XMLCite \textit{M. A. Henning} and \textit{O. R. Oellermann}, Australas. J. Comb. 23, 101--113 (2001; Zbl 0977.05072)