Proximity and Remoteness in Directed and Undirected Graphs

Abstract

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.