Back to Search
Start Over
Vertex-connectivity and eigenvalues of graphs.
- Source :
-
Linear Algebra & its Applications . Oct2019, Vol. 579, p72-88. 17p. - Publication Year :
- 2019
-
Abstract
- Let κ (G) , μ n − 1 (G) , λ 2 (G) and q 2 (G) denote the vertex-connectivity, the algebraic connectivity, the second largest adjacency eigenvalue, and the second largest signless Laplacian eigenvalue of G , respectively. In this paper, we prove that for an integer k > 0 and any simple graph G of order n with maximum degree Δ and minimum degree δ ≥ k , the vertex-connectivity κ (G) ≥ k if μ n − 1 (G) > H 2 (Δ , δ , k) or λ 2 (G) < δ − H 2 (Δ , δ , k) or q 2 (G) < 2 δ − H 2 (Δ , δ , k) , where H 2 (Δ , δ , k) = (k − 1) n Δ (n − k + 1) (k − 1) + 4 (δ − k + 2) (n − δ − 1) , which improves the result in [Appl. Math. Comput. 344–345 (2019) 141–149] and the result in [Electron. J. Linear Algebra 34 (2018) 428–443]. Analogue results involving μ n − 1 (G) , λ 2 (G) and q 2 (G) to characterize vertex-connectivity of regular graphs, triangle-free graphs and graphs with fixed girth are also presented. [ABSTRACT FROM AUTHOR]
- Subjects :
- *REGULAR graphs
*EIGENVALUES
*LINEAR algebra
*GEOMETRIC vertices
*MATHEMATICS
Subjects
Details
- Language :
- English
- ISSN :
- 00243795
- Volume :
- 579
- Database :
- Academic Search Index
- Journal :
- Linear Algebra & its Applications
- Publication Type :
- Academic Journal
- Accession number :
- 137777116
- Full Text :
- https://doi.org/10.1016/j.laa.2019.05.030