Graphs of given order and size and minimum algebraic connectivity

被引：13
作者：
Biyikoglu, Turker [2 ]
Leydold, Josef [1 ]
机构：
[1] WU Vienna Univ Econ & Business, Inst Stat & Math, A-1090 Vienna, Austria
[2] Isik Univ, Dept Math, TR-34980 Istanbul, Turkey
来源：
LINEAR ALGEBRA AND ITS APPLICATIONS | 2012年 / 436卷 / 07期
关键词：
Algebraic connectivity; Graph Laplacian; Fiedler vector; AutoGraphiX; TREES;
D O I：
10.1016/j.laa.2011.09.026
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
The structure of connected graphs of given size and order that have minimal algebraic connectivity is investigated. It is shown that they must consist of a chain of cliques. Moreover, an upper bound for the number of maximal cliques of size 2 or larger is derived. (C) 2011 Elsevier Inc. All rights reserved.
引用
收藏
页码：2067 / 2077
页数：11
相关论文
共 17 条
  • [1] [Anonymous], 2007, Lecture Notes in Mathematics
  • [2] The perturbed Laplacian matrix of a graph
    Bapat, RB
    Kirkland, SJ
    Pati, S
    Merris, R
    [J]. LINEAR & MULTILINEAR ALGEBRA, 2001, 49 (03) : 219 - 242
  • [3] Some results on the index of unicyclic graphs
    Belardo, Francesco
    Li Marzi, Enzo Maria
    Simic, Slobodan K.
    [J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 2006, 416 (2-3) : 1048 - 1059
  • [4] BELHAIZA S, 2005, GRAPH THEORY COMBINA, P1, DOI DOI 10.1007/0-387-25592-3_1
  • [5] Faber-Krahn type inequalities for trees
    Biyikoglu, Tuerker
    Leydold, Josef
    [J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 2007, 97 (02) : 159 - 174
  • [6] Algebraic connectivity and degree sequences of trees
    Biyikoglu, Tuerker
    Leydold, Josef
    [J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 2009, 430 (2-3) : 811 - 817
  • [7] Brand C, 2007, CROAT CHEM ACTA, V80, P193
  • [8] Brualdi RA., 1986, Publ. Inst. Math. (Beograd) (N.S.), V39, P45
  • [9] Davies EB, 2001, LINEAR ALGEBRA APPL, V336, P51
  • [10] Old and new results on algebraic connectivity of graphs
    de Abreu, Nair Maria Maia
    [J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 2007, 423 (01) : 53 - 73
12