Minimizing algebraic connectivity over connected graphs with fixed girth Original Research Article

Let Gn,g denote the class of all connected graphs on n vertices with fixed girth g. We prove that if n⩾3g−1, then the graph which uniquely minimizes the algebraic connectivity over Gn,g is the unicyclic “lollipop” graph Cn,g obtained by appending a g cycle to a pendant vertex of a path on n−g vertices. The characteristic set of Cn,g is also discussed. Throughout both algebraic and combinatorial techniques are used.