Upper Bounds on the average eccentricity of Graphs of Girth 66 and (C4(C_4, C5)C_5)-free Graphs

preprint2020arXivOpen access

Abstract

Let GG be a finite, connected graph. The eccentricity of a vertex vv of GG is the distance from vv to a vertex farthest from vv. The average eccentricity of GG is the arithmetic mean of the eccentricities of the vertices of GG. We show that the average eccentricity of a connected graph GG of girth at least six is at most 92⌈n2δ2−2δ+2⌉+7\frac{9}{2} \lceil \frac{n}{2δ^2 - 2δ+2} \rceil + 7, where nn is the order of GG and δδ its minimum degree. We construct graphs that show that whenever δ−1δ-1 is a prime power, then this bound is sharp apart from an additive constant. For graphs containing a vertex of large degree we give an improved bound. We further show that if the girth condition on GG is relaxed to GG having neither a 44-cycle nor a 55-cycle as a subgraph, then similar and only slightly weaker bounds hold.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.