algebraic connectivity greater than $1$

Question

Some Background

The algebraic connectivity of a graph $G$ is defined as the second smallest Laplacian eigenvalue of the graph and is denoted by $a(G)$.

It is known that $a(G)\le1$ if $G$ is a tree and in particular, when the tree is a star then equality holds. Further, if $G$ is a complete graph, then $a(G)=n$ where $n$ is the number of vertices of $G$.

My Question

Let $n-1< k<~ ^n\!C_2-n$. Then what is the maximum value of $k$ for which we can guarantee that if $G$ is a connected graph on $n$ vertices and $k$ edges, then $$a(G)<1?$$

Answer 1

1. $a$ should only increase if you take the star graph and add edges between "exterior" vertices, so that means the maximum of $a$ over graphs with $n$ vertices and $k$ edges is at least $1$ if $k \geq n-1$. (I'm not sure how to rigorously prove this, though I'm pretty confident that it is true.)
2. $a$ is necessarily $0$ if the graph is disconnected. This is guaranteed if $k<n-1$.

I think to make your question interesting you need some topological restrictions.