A bound on the algebraic connectivity of a graph in terms of the number of cutpoints

被引:49
作者
Kirkland, S [1 ]
机构
[1] Univ Regina, Dept Math & Stat, Regina, SK S4S 0A2, Canada
关键词
Laplacian matrix; algebraic connectivity; Perron value; cutpoint;
D O I
10.1080/03081080008818634
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
Let G be a graph on n vertices which has k cutpoints. For the case that 2 less than or equal to k less than or equal to n/2, we prove that the algebraic connectivity of G is at most 2(n - k)/(n - k + 2 + root (n - k)(2) + 4), and we explicitly characterize bound. the graphs attaining equality in this bound.
引用
收藏
页码:93 / 103
页数:11
相关论文
共 8 条
[1]  
[Anonymous], LINEAR ALGEBRA APPL
[2]  
Berman A., 1994, CLASSICS APPL MATH, DOI [10.1016/C2013-0-10361-3, 10.1137/1.9781611971262, DOI 10.1137/1.9781611971262]
[3]  
Fallat S, 1998, ELECTRON J LINEAR AL, V3, P48, DOI DOI 10.13001/1081-3810.10140913.05073
[4]  
FIEDLER M, 1975, CZECH MATH J, V25, P607
[5]  
FIEDLER M, 1973, CZECH MATH J, V23, P298
[6]  
GRONE R, 1987, CZECH MATH J, V37, P660
[7]  
Kirkland S., 1998, LINEAR MULTILINEAR A, V44, P131, DOI DOI 10.1080/03081089808818554
[8]  
Merris R., 1987, Linear Multilinear Algebra, V22, P115, DOI [DOI 10.1080/03081088708817827, DOI 10.1080/030810887088178270636.05021, 10.1080/03081088708817827]