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)\le \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)\le \frac{n}{6k}+\frac{19}{6}+\frac{k}{n}$. We demonstrate that, apart from an additive constant, this bound is best possible.