Minimizing algebraic connectivity over connected graphs with fixed girth (Q1613533)

Let \(G_{n,g}\) denote the class of all connected graphs with \(n\) vertices and girth \(g\), and let \(C_{n,g}\) denote the unicyclic ``lollipop'' graph obtained by joining with an edge a vertex of a \(g\)-cycle and a pendant vertex of a path on \(n-g\) vertices. Two of the present authors have earlier conjectured that \(C_{n,g}\) is the unique graph minimizing the algebraic connectivity over \(G_{n,g}\) and confirmed this conjecture for \(g=3\) (see \textit{S. Fallat} and \textit{S. Kirkland} [Electron. J. Linear Algebra 3, 48-74 (1998; Zbl 0913.05073)]). Resuming the results of the previous paper, the authors here confirm the conjecture for the case \(n\geq 3g-1\), as well as for the case \(g=4\). Further, for each fixed \(g\geq 5\) and \(n<3g-1\), they describe the class, containing less than \({n-g\choose g}\) graphs, for which the conjecture could be verified numerically using a standard mathematical package. Besides this, the authors also discuss the characteristic set of the graphs \(C_{n,g}\).