Let $D$ be a strongly connected digraph. The average distance $bar{sigma}(v)$ of a vertex $v$ of $D$ is the arithmetic mean of the distances from $v$ to all other vertices of $D$. The remoteness $rho(D)$ and proximity $pi(D)$ of $D$ are the maximum and the minimum of the average distances of the vertices of $D$, respectively. We obtain sharp upper and lower bounds on $pi(D)$ and $rho(D)$ as a function of the order $n$ of $D$ and describe the extreme digraphs for all the bounds. We also obtain such bounds for strong tournaments. We show that for a strong tournament $T$, we have $pi(T)=rho(T)$ if and only if $T$ is regular. Due to this result, one may conjecture that every strong digraph $D$ with $pi(D)=rho(D)$ is regular. We present an infinite family of non-regular strong digraphs $D$ such that $pi(D)=rho(D).$ We describe such a family for undirected graphs as well.
Download