On algebraic connectivity augmentation

Suppose that G is an undirected graph, and that H is a spanning subgraph of G^c whose edges induce a subgraph on p vertices. We consider the expression α(G∪H)-α(G), where α denotes the algebraic connectivity. Specifically, we provide upper and lower bounds on α(G∪H)-α(G) in terms of p, and characterise the corresponding equality cases. We also discuss the density of the expression α(G∪H)-α(G) in the interval 0,p]. A bound on α(G∪H)-α(G) is provided in a special case, and several examples are considered.