Bounds for eccentricity-based parameters of graphs

Abstract

The \emph{eccentricity} of a vertex $u$ in a graph $G$, denoted by $e_G(u)$, is the maximum distance from $u$ to other vertices in $G$. We study extremal problems for the average eccentricity and the first and second Zagreb eccentricity indices, denoted by ${\sigma }_0(G)$, ${\sigma }_1(G)$, and ${\sigma }_2(G)$, respectively. These are defined by ${\sigma }_0(G)=\frac{1}{|V(G)|}{\sum }_{u\in V(G)}{e}_G(u)$, ${\sigma }_1(G)={\sum }_{u\in V(G)}{e}_G^2(u)$, and ${\sigma }_2(G)={\sum }_{uv\in E(G)}{e}_G(u)e_G(v)$. We study lower and upper bounds on these parameters among $n$-vertex connected graphs with fixed diameter, chromatic number, clique number, or matching number. Most of the bounds are sharp, with the corresponding extremal graphs characterized.

27 pages