Upper Bounds on the average eccentricity of Graphs of Girth $6$ and $(C_4$, $C_5)$-free Graphs

Abstract

Let $G$ be a finite, connected graph. The eccentricity of a vertex $v$ of $G$ is the distance from $v$ to a vertex farthest from $v$. The average eccentricity of $G$ is the arithmetic mean of the eccentricities of the vertices of $G$. We show that the average eccentricity of a connected graph $G$ of girth at least six is at most $\frac{9}{2}\lceil \frac{n}{2{\delta }^2-2\delta +2}\rceil +7$, where $n$ is the order of $G$ and $\delta$ its minimum degree. We construct graphs that show that whenever $\delta -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 $G$ is relaxed to $G$ having neither a $4$-cycle nor a $5$-cycle as a subgraph, then similar and only slightly weaker bounds hold.

14 pages