Augmenting the algebraic connectivity for certain families of graphs

In this work we compare solutions of two distinct algorithms that try to increase the value of the algebraic connectivity of a given graph by choosing, with different strategies, edges to be included. Eccentricity and Perturbation Heuristics were considered, as well as random graphs and special families of trees being inputs of those algorithms. As conclusions of the reported experiments, the Eccentricity Heuristic obtains good results when compared with Perturbation Heuristic and a conjecture about broom trees is presented. (C) 2018 Elsevier B.V. All rights reserved.