TY - JOUR
ID - 13543
TI - New bounds on proximity and remoteness in graphs
JO - Communications in Combinatorics and Optimization
JA - CCO
LA - en
SN - 2538-2128
AU - Dankelmann, P.
AD - University of Johannesburg
Y1 - 2016
PY - 2016
VL - 1
IS - 1
SP - 29
EP - 41
KW - diameter
KW - radius
KW - proximity
KW - remoteness
KW - distance
DO - 10.22049/cco.2016.13543
N2 - 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.
UR - http://comb-opt.azaruniv.ac.ir/article_13543.html
L1 - http://comb-opt.azaruniv.ac.ir/article_13543_99e338e777d53b2fb451bb25a4de0578.pdf
ER -