Average Distance in \(k\)-Connected Tournaments

Abstract

The average distance \(\mu(D)\) of a strong digraph \(D\) is the average of the distances between all ordered pairs of distinct vertices of \(D\). Plesnik \([6]\) proved that if \(D\) is a strong tournament of order \(n\), then \(\mu(D) \leq \frac{n+4}{6} + \frac{1}{n}\). In this paper, we show that if \(D\) is a \(k\)-connected tournament of order \(n\), then \(\mu(D) \leq \frac{n}{6k} + \frac{19}{6} + \frac{k}{n}\). We demonstrate that, apart from an additive constant, this bound is best possible.