New bounds on proximity and remoteness in graphs

Document Type : Original paper


University of Johannesburg


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.


Main Subjects