Average eccentricity, minimum degree and maximum degree in graphs

P. Dankelmann, F. J. Osaye

Research output: Contribution to journalArticlepeer-review

8 Citations (Scopus)

Abstract

Let G be a connected finite graph with vertex set V(G). The eccentricity e(v) of a vertex v is the distance from v to a vertex farthest from v. The average eccentricity of G is defined as 1|V(G)|∑v∈V(G)e(v). We show that the average eccentricity of a connected graph of order n, minimum degree δ and maximum degree Δ does not exceed 94n-Δ-1δ+1(1+Δ-δ3n)+7, and this bound is sharp apart from an additive constant. We give improved bounds for triangle-free graphs and for graphs not containing 4-cycles.

Original languageEnglish
Pages (from-to)697-712
Number of pages16
JournalJournal of Combinatorial Optimization
Volume40
Issue number3
DOIs
Publication statusPublished - 1 Oct 2020

Keywords

  • Average eccentricity
  • Distance
  • Eccentricity
  • Graph
  • Maximum degree
  • Minimum degree

ASJC Scopus subject areas

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'Average eccentricity, minimum degree and maximum degree in graphs'. Together they form a unique fingerprint.

Cite this