Eccentricity and algebraic connectivity of graphs

Let G be a graph on n nodes with algebraic connectivity λ₂. The eccentricity of a node is defined as the length of a longest shortest path starting at that node. If s_ denotes the number of nodes of eccentricity at most , then for ≥ 2, λ₂ ≥ 4 \, s_ (-2+4/n) \, n² . As a corollary, if d denotes the diameter of G, then λ₂ ≥ 4 (d-2+4/n) \, n . It is also shown that λ₂ ≥ s_ 1+ (e(G^)-m) , where m and e(G⁾ denote the number of edges in G and in the -th power of G, respectively.