New bounds on proximity and remoteness in graphs

Abstract

The average distance of a vertex $v$ of a connected graph $G$is the arithmetic mean of the distances from $v$ to allother vertices of $G$. The proximity $pi(G)$ and the remoteness $rho(G)$of $G$ are defined as the minimum and maximum averagedistance of the vertices of $G$. In this paper we investigate the difference between proximity or remoteness and the classical distanceparameters diameter and radius. Among other results we show that in a graph of order$n$ and minimum degree $delta$ the difference betweendiameter and proximity and the difference betweenradius 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 byAouchiche and Hansen cite{AouHan2011} in terms oforder alone by about a factor of $frac{3}{delta+1}$. We further give lower bounds on the remoteness interms of diameter or radius. Finally we show thatthe average distance of a graph, i.e., the average ofthe distances between all pairs of vertices, cannotexceed twice the proximity.