The average eccentricity, spanning trees of plane graphs, size and order

Patrick Ali, Peter Dankelmann, Megan J. Morgan, Simon Mukwembi, Henda Swart, Tomás Vetrík

Research output: Contribution to journalArticlepeer-review

9 Citations (Scopus)


Let G be a connected graph. The eccentricity, ECG(v), of a vertex v V(G) is the maximum distance between v and any other vertex in G, and the average eccentricity, avec(G), of G is the mean of the eccentricities of vertices in G. We prove that every 3-connected plane graph of order p and maximum face length I has a spanning tree T with average eccentricity at most p/4 +(25/48 l/p+ 5/6p+ 5/4) +1/3p+ 1. Furthermore, we extend this result to 4- and 5-connected plane graphs. We also construct graphs to show that the bounds are asymptotically sharp. In addition, we establish an asymptotically sharp upper bound on the average eccentricity of graphs in terms of order and size.

Original languageEnglish
Pages (from-to)37-49
Number of pages13
JournalUtilitas Mathematica
Publication statusPublished - Jun 2018


  • Average eccentricity
  • Planar graph
  • Spanning tree

ASJC Scopus subject areas

  • Statistics and Probability
  • Statistics, Probability and Uncertainty
  • Applied Mathematics


Dive into the research topics of 'The average eccentricity, spanning trees of plane graphs, size and order'. Together they form a unique fingerprint.

Cite this