%0 Journal Article
%T New bounds on proximity and remoteness in graphs
%J Communications in Combinatorics and Optimization
%I Azarbaijan Shahid Madani University
%Z 2538-2128
%A Dankelmann, P.
%D 2016
%\ 06/01/2016
%V 1
%N 1
%P 29-41
%! New bounds on proximity and remoteness in graphs
%K diameter
%K radius
%K proximity
%K remoteness
%K distance
%R 10.22049/cco.2016.13543
%X 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.
%U http://comb-opt.azaruniv.ac.ir/article_13543_99e338e777d53b2fb451bb25a4de0578.pdf