On algebraic connectivity augmentation

Abstract: Suppose that G is an undirected graph, and that H is a spanning subgraph of whose edges induce a subgraph on p vertices. We consider the expression , where denotes the algebraic connectivity. Specifically, we provide upper and lower bounds on in terms of p, and characterise the corresponding equality cases. We also discuss the density of the expression in the interval . A bound on is provided in a special case, and several examples are considered. [Copyright &y& Elsevier]