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.
Dankelmann, P. (2016). New bounds on proximity and remoteness in graphs. Communications in Combinatorics and Optimization, 1(1), 29-41. doi: 10.22049/cco.2016.13543
MLA
P. Dankelmann. "New bounds on proximity and remoteness in graphs". Communications in Combinatorics and Optimization, 1, 1, 2016, 29-41. doi: 10.22049/cco.2016.13543
HARVARD
Dankelmann, P. (2016). 'New bounds on proximity and remoteness in graphs', Communications in Combinatorics and Optimization, 1(1), pp. 29-41. doi: 10.22049/cco.2016.13543
VANCOUVER
Dankelmann, P. New bounds on proximity and remoteness in graphs. Communications in Combinatorics and Optimization, 2016; 1(1): 29-41. doi: 10.22049/cco.2016.13543