Variable Neighborhood Search for Extremal Graphs. 11. Bounds on Algebraic Connectivity

The algebraic connectivity a(G) of a graph G = (V,E) is the second smallest eigenvalue of its Laplacian matrix. Using the AutoGraphiX (AGX) system, extremal graphs for algebraic connectivity of G in function of its order n = |V| and size m = |E| are studied. Several conjectures on the structure of those graphs, and implied bounds on the algebraic connectivity, are obtained. Some of them are proved.