Maximizing Algebraic Connectivity Over Unicyclic Graphs

We consider the class of unicyclic graphs on n vertices with girth g, and over that class, we attempt to determine which graph maximizes the algebraic connectivity. When g is fixed, we show that there is an N such that for each n>N, the maximizing graph consists of a g cycle with n−g pendant vertices adjacent to a common vertex on the cycle. We also provide a bound on N. On the other hand, when g is large relative to n, we show that this graph does not maximize the algebraic connectivity, and we give a partial discussion of the nature of the maximizing graph in that situation.