G-2004-68
Variable Neighborhood Search for Extremal Graphs. 11. Bounds on Algebraic Connectivity
Slim Belhaiza, Nair Maria Maia de Abreu, Pierre Hansen et Carla Silva Oliveira
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.
Paru en août 2004 , 18 pages