Augmenting the algebraic connectivity for certain families of graphs

被引：1
|
作者：
Justel, Claudia [1 ]
Rocha, Carlos [1 ]
Chaves, Emanuelle [1 ]
Chaves, Anderson [1 ]
Avelino, Geraldo [1 ]
机构：
[1] Inst Mil Engn, Rio De Janeiro, Brazil
来源：
DISCRETE APPLIED MATHEMATICS | 2019年 / 253卷
关键词：
Graph spectra; Laplacian matrix; Algebraic connectivity; Approximated algorithm;
D O I：
10.1016/j.dam.2018.03.069
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
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.
引用
收藏
页码：51 / 60
页数：10
相关论文
共 50 条
  • [21] Lower bounds for the algebraic connectivity of graphs with specified subgraphs
    Stanic, Zoran
    ELECTRONIC JOURNAL OF GRAPH THEORY AND APPLICATIONS, 2021, 9 (02) : 257 - 263
  • [22] On minimum algebraic connectivity of graphs whose complements are bicyclic
    Liu, Jia-Bao
    Javaid, Muhammad
    Raza, Mohsin
    Saleem, Naeem
    OPEN MATHEMATICS, 2019, 17 : 1490 - 1502
  • [23] Algebraic connectivity of weighed graphs under shifting components
    Guan, Yu
    PROCEEDINGS OF THE THIRD INTERNATIONAL WORKSHOP ON MATRIX ANALYSIS AND APPPLICATIONS, VOL 1, 2009, : 173 - 176
  • [24] Algebraic Connectivity of Power Graphs of Finite Cyclic Groups
    Rather, Bilal Ahmad
    MATHEMATICS, 2024, 12 (14)
  • [25] ALGEBRAIC CONNECTIVITY OF WEIGHED GRAPHS UNDER SHIFTING COMPONENTS
    Guan, Yu
    Xu, Guanghui
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2010, 2 (03) : 263 - 275
  • [26] On graphs with algebraic connectivity equal to minimum edge density
    Fallat, SM
    Kirkland, S
    Pati, S
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2003, 373 : 31 - 50
  • [27] The sharpness of a lower bound on the algebraic connectivity for maximal graphs
    Kirkland, SJ
    Molitierno, JJ
    Neumann, M
    LINEAR & MULTILINEAR ALGEBRA, 2001, 48 (03) : 237 - 246
  • [28] On the algebraic connectivity of graphs as a function of genus
    Molitierno, Jason J.
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2006, 419 (2-3) : 519 - 531
  • [29] Algebraic connectivity ratio of Ramanujan graphs
    Olfati-Saber, Reza
    2007 AMERICAN CONTROL CONFERENCE, VOLS 1-13, 2007, : 687 - 692
  • [30] The algebraic connectivity of graphs with given circumference
    Xue, Jie
    Lin, Huiqiu
    Shu, Jinlong
    THEORETICAL COMPUTER SCIENCE, 2019, 772 : 123 - 131
12345