THE VERTEX CONNECTIVITY AND THE THIRD LARGEST EIGENVALUE IN REGULAR (MULTI-)GRAPHS

被引：0
作者：
Ma, Tingyan [1 ,2 ]
Wang, Ligong [1 ,2 ]
Hu, Yang [1 ,2 ]
机构：
[1] Northwestern Polytech Univ, Sch Math & Stat, Xian 710129, Shaanxi, Peoples R China
[2] Northwestern Polytech Univ, Xian Budapest Joint Res Ctr Combinator, Xian 710129, Shaanxi, Peoples R China
来源：
ELECTRONIC JOURNAL OF LINEAR ALGEBRA | 2024年 / 40卷
关键词：
Eigenvalue; Vertex connectivity; Regular graph; Multigraph; DISJOINT SPANNING-TREES; ALGEBRAIC CONNECTIVITY; GRAPHS;
D O I：
暂无
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
Let G be a simple graph or a multigraph. The vertex connectivity kappa(G) of G is the minimum size of a vertex set S such that G -S is disconnected or has only one vertex. We denote by lambda(3)(G) the third largest eigenvalue of the adjacency matrix of G. In this paper, we present an upper bound for lambda(3)(G) in a d-regular (multi-)graph G which guarantees that kappa(G) >= t + 1, which is based on the result of Abiad et al. [Spectral bounds for the connectivity of regular graphs with given order. Electron. J. Linear Algebra 34:428-443, 2018]. Furthermore, we improve the upper bound for lambda 3(G) in a d-regular multigraph which assures that kappa(G) >= 2.
引用
收藏
页码：322 / 332
页数：11
相关论文
共 24 条
[11]  
FIEDLER M, 1973, CZECH MATH J, V23, P298
[12]   INTERLACING EIGENVALUES AND GRAPHS [J].
HAEMERS, WH .
LINEAR ALGEBRA AND ITS APPLICATIONS, 1995, 226 :593-616
[13]   Vertex-connectivity and eigenvalues of graphs [J].
Hong, Zhen-Mu ;
Xia, Zheng-Jiang ;
Lai, Hong-Jian .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2019, 579 (72-88) :72-88
[14]  
Horn Roger A., 2012, Matrix Analysis
[15]   Spectral conditions for edge connectivity and spanning tree packing number in (multi-)graphs [J].
Hu, Yang ;
Wang, Ligong ;
Duan, Cunxiang .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2023, 664 :324-348
[16]   On graphs with equal algebraic and vertex connectivity [J].
Kirkland, SJ ;
Molitierno, JJ ;
Neumann, M ;
Shader, BL .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2002, 341 (1-3) :45-56
[17]   The smallest values of algebraic connectivity for unicyclic graphs [J].
Li, Jianxi ;
Guo, Ji-Ming ;
Shiu, Wai Chee .
DISCRETE APPLIED MATHEMATICS, 2010, 158 (15) :1633-1643
[18]   On the third largest eigenvalue of a graph [J].
Liu, BL ;
Bo, Z .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2000, 317 (1-3) :193-200
[19]   Edge-disjoint spanning trees and eigenvalues [J].
Liu, Qinghai ;
Hong, Yanmei ;
Lai, Hong-Jian .
LINEAR ALGEBRA AND ITS APPLICATIONS, 2014, 444 :146-151
[20]   Vertex-connectivity and eigenvalues of graphs with fixed girth [J].
Liu, Ruifang ;
Lai, Hong-Jian ;
Tian, Yingzhi ;
Wu, Yang .
APPLIED MATHEMATICS AND COMPUTATION, 2019, 344 :141-149
123