Eccentricity and algebraic connectivity of graphs

Abstract

Let $G$ be a graph on $n$ nodes with algebraic connectivity $\hat{I}{»}_2$. The eccentricity of a node is defined as the length of a longest shortest path starting at that node. If $s_{\ell }$ denotes the number of nodes of eccentricity at most $\ell$, then for $\ell \ge 2$, $$\hat{I}{»}_2\ge \frac{4s_{\ell }}{(\ell -2+\frac{4}{n})n^2}.$$ As a corollary, if $d$ denotes the diameter of $G$, then $$\hat{I}{»}_2\ge \frac{4}{(d-2+\frac{4}{n})n}.$$ It is also shown that $$\hat{I}{»}_2\ge \frac{s_{\ell }}{1+\ell \left(e(G^{\ell })-m\right)},$$ where $m$ and $e(G^{\ell })$ denote the number of edges in $G$ and in the $\ell$-th power of $G$, respectively.

Published version