Eigenvalues and edge-connectivity of regular graphs

被引:47
作者
Cioaba, Sebastian M. [1 ]
机构
[1] Univ Delaware, Dept Math Sci, Newark, DE 19716 USA
关键词
Connectivity; Eigenvalues; Regular graph; ALGEBRAIC CONNECTIVITY;
D O I
10.1016/j.laa.2009.08.029
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
In this paper, we show that if the second largest eigenvalue of a d-regular graph is less than d - 2(k-1)/d+1, then the graph is k-edge-connected. When k is 2 or 3, we prove stronger results. Let rho(d) denote the largest root of x(3) - (d-3)x(2) - (3d - 2)x - 2 = 0. We show that if the second largest eigenvalue of a d-regular graph G is less than rho(d), then G is 2-edge-connected and we prove that if the second largest eigenvalue of G is less than d-3+root(d+3)(2) - 16/2, then G is 3-edge-connected. (C) 2009 Elsevier Inc. All rights reserved.
引用
收藏
页码:458 / 470
页数:13
相关论文
共 15 条
[1]  
Brouwer A.E., 1989, DISTANCE REGULAR GRA
[2]  
Brouwer A.E., 1996, CWI Q, V9, P37
[3]   Eigenvalues and perfect matchings [J].
Brouwer, AE ;
Haemers, WH .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2005, 395 :155-162
[4]   The vertex-connectivity of a distance-regular graph [J].
Brouwer, Andries E. ;
Koolen, Jack H. .
EUROPEAN JOURNAL OF COMBINATORICS, 2009, 30 (03) :668-673
[5]   Minimum cuts, girth and a spectral threshold [J].
Chandran, LS .
INFORMATION PROCESSING LETTERS, 2004, 89 (03) :105-110
[6]   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
[7]  
FIEDLER M, 1973, CZECH MATH J, V23, P298
[8]  
Godsil C., 2001, Algebraic graph theory
[9]   INTERLACING EIGENVALUES AND GRAPHS [J].
HAEMERS, WH .
LINEAR ALGEBRA AND ITS APPLICATIONS, 1995, 226 :593-616
[10]  
Haemers Willem, 1979, Eigenvalue Techniques in Design and Graph Theory