Proximity and remoteness in directed and undirected graphs (Q2222950)

For a vertex \(v\) of a strongly connected digraph \(D\), the average distance \(\overline{\sigma}(v)\) 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. Both parameters were introduced by \textit{B. Zelinka} [Arch. Math., Brno 4, 87--95 (1968; Zbl 0206.26105)] and, independently, by \textit{M. Aouchiche} and \textit{P. Hansen} [Networks 58, No. 2, 95--102 (2011; Zbl 1232.05062)] for undirected graphs. In the paper under review, the authors extend their study to directed graph, and obtain sharp upper and lower bounds on both parameters in terms of the order of a digraph. As a special case, tournaments are considered. It is shown that for a strong tournament remoteness and proximity coincide if and only if the tournament is regular. In addition, an infinite family of non-regular strong digraphs \(D\) such that \(\rho(D)=\pi(D)\) is presented.