New bounds on proximity and remoteness in graphs

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 π(G) and the remoteness ρ(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 δ the difference between diameter and proximity and the difference between radius and proximity cannot exceed [Formula presented] and [Formula presented], respectively, for constants c₁ and c₂ which depend on δ but not on n. These bounds improve bounds by Aouchiche and Hansen [3] in terms of order alone by about a factor of 3 δ+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.