ELA, Volume 3, pp. 48-74, April 1998, abstract.
Extremizing Algebraic Connectivity Subject to Graph Theoretic Constraints
Shaun Fallat and Steve Kirkland
The main problem of interest is to investigate how the algebraic
connectivity of a weighted connected graph behaves when the graph is
perturbed by removing one or more connected components at a fixed vertex
and replacing this collection by a single connected component.
This analysis leads to exhibiting the unique (up to isomorphism) trees on
n vertices with specified diameter that maximize and minimize the
algebraic connectivity over all such trees. When the radius of a graph is
the specified constraint the unique minimizer of the algebraic connectivity
over all such graphs is also determined. Analogous results are proved for
unicyclic graphs with fixed girth. In particular, the unique minimizer and
maximizer of the algebraic connectivity is given over all such graphs with
girth 3.