Proximity, remoteness and minimum degree

Research output: Contribution to journalArticlepeer-review

14 Citations (Scopus)


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 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 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.

Original languageEnglish
Pages (from-to)223-228
Number of pages6
JournalDiscrete Applied Mathematics
Publication statusPublished - 31 Mar 2015


  • Distance
  • Minimum degree
  • Proximity
  • Remoteness
  • Total distance
  • Transmission

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Proximity, remoteness and minimum degree'. Together they form a unique fingerprint.

Cite this