Proximity, remoteness and girth in graphs

M. Aouchiche, P. Hansen

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)

Abstract

The proximity π of a graph G is the minimum average distance from a vertex of G to all others. Similarly, the remoteness of G is the maximum average distance from a vertex to all others. The girth g of a graph G is the length of its smallest cycle. In this paper, we provide and prove sharp lower and upper bounds, in terms of the order n of G, on the difference, the sum, the ratio and the product of the proximity and the girth. We do the same for the remoteness and the girth, except for the lower bound on ρ/g, which is already known.

Original languageEnglish
Pages (from-to)31-39
Number of pages9
JournalDiscrete Applied Mathematics
Volume222
DOIs
Publication statusPublished - May 11 2017
Externally publishedYes

Keywords

  • Extremal graph
  • Girth
  • Proximity
  • Remoteness

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Proximity, remoteness and girth in graphs'. Together they form a unique fingerprint.

Cite this