Nordhaus-Gaddum relations for proximity and remoteness in graphs

M. Aouchiche, P. Hansen

Research output: Contribution to journalArticlepeer-review

27 Citations (Scopus)


The transmission of a vertex in a connected graph is the sum of all distances from that vertex to the others. It is said to be normalized if divided by n - 1, where n denotes the order of the graph. The proximity of a graph is the minimum normalized transmission, while the remoteness is the maximum normalized transmission. In this paper, we give Nordhaus-Gaddum-type inequalities for proximity and remoteness in graphs. The extremal graphs are also characterized for each case.

Original languageEnglish
Pages (from-to)2827-2835
Number of pages9
JournalComputers and Mathematics with Applications
Issue number8
Publication statusPublished - Apr 2010
Externally publishedYes


  • Extremal graph
  • Nordhaus-Gaddum
  • Proximity
  • Remoteness

ASJC Scopus subject areas

  • Modelling and Simulation
  • Computational Theory and Mathematics
  • Computational Mathematics


Dive into the research topics of 'Nordhaus-Gaddum relations for proximity and remoteness in graphs'. Together they form a unique fingerprint.

Cite this