Proximity, remoteness and minimum degree

The average distance σ¯(v) of a vertex v of a connected graph G is the average of the distances between v and all other vertices. The remoteness ρ(G) and proximity π(G) of G are defined as max_vεV(G)σ¯(v) and min_vεV(G)σ¯(v), respectively. Zelinka (1968) and, independently, Aouchiche and Hansen (2011) showed that the proximity and remoteness of a connected graph of order n are bounded by approximately n4 and n2, respectively, and that the difference between the remoteness and proximity is bounded by approximately n4. We show that for graphs of minimum degree δ, where δ≥2, all three bounds can be improved by a factor of about 3δ+1. Our bounds are sharp except for an additive constant.