New bounds on proximity and remoteness in graphs

The average distance of a vertex $v$ of a connected graph $G$ is the arithmetic mean of the distances from $v$ to all other vertices of $G$. The proximity $pi(G)$ and the remoteness $rho(G)$ of $G$ are defined as the minimum and maximum average distance of the vertices of $G$. In this paper we investigate the difference between proximity or remoteness and the classical distance parameters diameter and radius. Among other results we show that in a graph of order $n$ and minimum degree $delta$ the difference between diameter and proximity and the difference between radius and proximity cannot exceed $frac{9n}{4(delta+1)}+c_1$ and $frac{3n}{4(delta+1)}+c_2$, respectively, for constants $c_1$ and $c_2$ which depend on $delta$ but not on $n$. These bounds improve bounds by Aouchiche and Hansen cite{AouHan2011} in terms of order alone by about a factor of $frac{3}{delta+1}$. We further give lower bounds on the remoteness in terms of diameter or radius. Finally we show that the average distance of a graph, i.e., the average of the distances between all pairs of vertices, cannot exceed twice the proximity.