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 [J].

Bapat, RB ;

Kirkland, SJ ;

Pati, S ;

Merris, R .

LINEAR & MULTILINEAR ALGEBRA, 2001, 49 (03) :219-242

[3] Some results on the index of unicyclic graphs [J].

Belardo, Francesco ;

Li Marzi, Enzo Maria ;

Simic, Slobodan K. .

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 [J].

Biyikoglu, Tuerker ;

Leydold, Josef .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2007, 97 (02) :159-174

[6] Algebraic connectivity and degree sequences of trees [J].

Biyikoglu, Tuerker ;

Leydold, Josef .

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 [J].

de Abreu, Nair Maria Maia .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2007, 423 (01) :53-73

← 1 2 →