Minimizing algebraic connectivity over connected graphs with fixed girth

被引：33
|
作者：
Fallat, SM [1 ]
Kirkland, S [1 ]
Pati, S [1 ]
机构：
[1] Univ Regina, Dept Math & Stat, Regina, SK S4S 0A2, Canada
来源：
DISCRETE MATHEMATICS | 2002年 / 254卷 / 1-3期
基金：
加拿大自然科学与工程研究理事会;
关键词：
Laplacian matrix; algebraic connectivity; girth; unicyclic graph; Perron value; characteristic set;
D O I：
10.1016/S0012-365X(01)00355-7
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
Let G,g denote the class of all connected graphs on n vertices with fixed girth g. We prove that if n greater than or equal to 3g-1, then the graph which uniquely minimizes the algebraic connectivity over G,g is the unicyclic "lollipop" graph C-n,C-g obtained by appending a g cycle to a pendant vertex of a path on n - g vertices. The characteristic set of C-n,C-g is also discussed. Throughout both algebraic and combinatorial techniques are used. (C) 2002 Elsevier Science B.V. All rights reserved.
引用
收藏
页码：115 / 142
页数：28
相关论文
共 50 条
  • [31] Distributed Estimation and Control of Algebraic Connectivity Over Random Graphs
    Di Lorenzo, Paolo
    Barbarossa, Sergio
    IEEE TRANSACTIONS ON SIGNAL PROCESSING, 2014, 62 (21) : 5615 - 5628
  • [32] On connected signed graphs with rank equal to girth
    Wu, Qi
    Lu, Yong
    Tam, Bit-Shun
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2022, 651 : 90 - 115
  • [33] An upper bound on the algebraic connectivity of outerplanar graphs
    Molitierno, Jason J.
    DISCRETE MATHEMATICS, 2017, 340 (08) : 1851 - 1870
  • [34] THE ALGEBRAIC CONNECTIVITY OF GRAPHS WITH GIVEN STABILITY NUMBER
    Zhang, Shunzhe
    Zhao, Qin
    Liu, Huiqing
    ELECTRONIC JOURNAL OF LINEAR ALGEBRA, 2017, 32 : 184 - 190
  • [35] Augmenting the algebraic connectivity for certain families of graphs
    Justel, Claudia
    Rocha, Carlos
    Chaves, Emanuelle
    Chaves, Anderson
    Avelino, Geraldo
    DISCRETE APPLIED MATHEMATICS, 2019, 253 : 51 - 60
  • [36] ALGEBRAIC CONNECTIVITY OF LOLLIPOP GRAPHS: A NEW APPROACH
    Kalita, D.
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2014, 6 (02)
  • [37] The algebraic connectivity of barbell graphs
    Song, Xiaodi
    Zhang, Shenggui
    Chen, Xinzhuang
    Gao, Shanshan
    DISCRETE MATHEMATICS, 2024, 347 (07)
  • [38] The algebraic connectivity of lollipop graphs
    Guo, Ji-Ming
    Shiu, Wai Chee
    Li, Jianxi
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2011, 434 (10) : 2204 - 2210
  • [39] Normalized algebraic connectivity of graphs
    Liu, Hongjuan
    Li, Honghai
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2019, 11 (03)
  • [40] The smallest values of algebraic connectivity for unicyclic graphs
    Li, Jianxi
    Guo, Ji-Ming
    Shiu, Wai Chee
    DISCRETE APPLIED MATHEMATICS, 2010, 158 (15) : 1633 - 1643
12345