Average eccentricity, minimum degree and maximum degree in graphs

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 $\frac{1}{|V(G)|}{\sum }_{v\in V(G)}e(v)$. We show that the average eccentricity of a connected graph of order $n$, minimum degree $\delta$ and maximum degree $\Delta$ does not exceed $\frac{9}{4}\frac{n-\Delta -1}{\delta +1}(1+\frac{\Delta -\delta }{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 a $4$-cycles.

15 pages, 3 figures