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

Let \(G\) be a simple graph on \(n\) vertices with the Laplacian matrix \(L\) and the algebraic connectivity \(\mu(G)\). Further, let \(L^\#=(l_{ij}^\#)\) be the group inverse of \(L\), and let \[ {\mathcal Z}(L^\#):= (1/2) \max_{1\leq i,j\leq n} \sum_{s=1}^n |l_{i,s}^\#-l_{j,s}^\#|. \] It was observed by \textit{S. J. Kirkland, M. Neumann} and \textit{B. L. Shader} [SIAM J. Matrix Anal. Appl. 18, No. 4, 827-841 (1997; Zbl 0889.15004)] that \(1/{\mathcal Z}(L^\#)\leq\mu(G).\) The present paper deals with the case of equality in this inequality. It was already shown by \textit{S. J. Kirkland, M. Neumann} and \textit{B. L. Shader} [Czech. Math. J. 48, No. 1, 65-76 (1998; Zbl 0931.15013)] that if \(G\) is a tree, the equality holds if and only if \(G\) is a star. A maximal graph is a graph whose degree sequence is not majorized by the degree sequence of any other graph. The authors show that the equality always holds if \(G\) is a maximal graph (as it happens, a star is a maximal graph, so that the present result generalizes the result on trees). However, the authors supply an example showing that for a graph \(G\), it is possible that \(1/{\mathcal Z}(L^\#)=\mu(G)\) without \(G\) being a maximal graph, so that the characterization of the case of equality is still open.