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.