Proximity, remoteness and minimum degree

The average distance σ¯(v) of a vertex vv of a connected graph GG is the average of the distances between vv and all other vertices. The remoteness ρ(G)ρ(G) and proximity π(G)π(G) of GG are defined as maxv∈V(G)σ¯(v) and minv∈V(G)σ¯(v), respectively. Zelinka (1968) and, independently, Aouchiche and Hansen (2011) showed that the proximity and remoteness of a connected graph of order nn 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δ≥2, all three bounds can be improved by a factor of about 3δ+1. Our bounds are sharp except for an additive constant.