Proximity, remoteness and minimum degree
The average distance ?  ( v ) of a vertex v v of a connected graph G G is the average of the distances between v v and all other vertices. The remoteness ?(G) ? ( G ) and proximity ?(G) ? ( G ) of G 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 n are bounded by approximately n 4 and n 2 , respectively, and that the difference between the remoteness and proximity is bounded by approximately n 4 . 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.
proximity remoteness minimum degree distance transmission total distance