The average connectivity of regular multipartite tournaments (Q2712515)

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\).