On the Average of the Eccentricities of a Graph

Abstract

Let $G=(V,\,E)$ be a simple connected graph of order $n$ with $m$
edges. Also let $e_G(v_i)$ be the eccentricity of a vertex $v_i$ in
$G$.
 We can assume that $e_G(v_1)\geq e_G(v_2)\geq \cdots\geq e_G(v_{n-1})\geq e_G(v_n).$ The average eccentricity of a graph $G$ is
 the mean value of eccentricities of vertices of $G$,
     $$avec(G)=\frac{1}{n}\,\sum\limits^n_{i=1}\,e_G(v_i)\,.$$
 Let $\gamma=\gamma_G$ be the largest positive integer such that
   $$e_G(v_{\gamma_G})\geq avec(G).$$
 In this paper, we study on the value of $\gamma_G$ of a graph $G$. For any tree $T$ of order $n$, we prove that $2\leq \gamma_T\leq n-1$ and characterize the extremal graphs.
 Moreover, we prove that for any graph $G$ of order $n$, $2\leq \gamma_G\leq n$ and characterize the extremal graphs. Finally some Nordhaus-Gaddum type results are obtained on $\gamma_G$ of general graphs $G$.