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 all‎ ‎other vertices of $G$‎. ‎The proximity $\pi(G)$ and the remoteness $\rho(G)$‎ ‎of $G$ are defined as the minimum and maximum‎, ‎respectively‎, ‎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‎.

Keywords

• proximity; remoteness; diameter; radius; average distance; Wiener index.