The sharpness of a lower bound on the algebraic connectivity for maximal graphs

Let B be an undirected unweighted graph on n vertices and let L be its Lapl acian matrix. It is known that if L-# = (e(ij)((#))) is the group inverse o f L, then for Z(L-#) := (1/2) max(1 less than or equal toi,j less than or equal ton) Sigm a (n)(s=1) /l(i,s)((#)) - l(j,s)((#))/, is a lower bound on the algebraic connectivity mu (G) Of S. Merris has intr oduced and characterized the class of all maximal graphs of all orders. The se are graphs whose degree sequence is not majorized by the degree sequence of any other graph. Here we show that if G is a maximal graph and L is its Laplacian, then 1/Z(L-#) = mu (G). We provide an example to show that the converse of this result is not valid.