Title
Spectral Bounds For The Connectivity Of Regular Graphs With Given Order
Keywords
Algebraic connectivity; Edge-connectivity; Regular multigraph; Second-largest eigenvalue; Vertex-connectivity
Abstract
The second-largest eigenvalue and second-smallest Laplacian eigenvalue of a graph are measures of its connectivity. These eigenvalues can be used to analyze the robustness, resilience, and synchronizability of networks, and are related to connectivity attributes such as the vertex-and edge-connectivity, isoperimetric number, and characteristic path length. In this paper, two upper bounds are presented for the second-largest eigenvalues of regular graphs and multigraphs of a given order which guarantee a desired vertex-or edge-connectivity. The given bounds are in terms of the order and degree of the graphs, and hold with equality for infinite families of graphs. These results answer a question of Mohar.
Publication Date
1-1-2018
Publication Title
Electronic Journal of Linear Algebra
Volume
34
Number of Pages
428-443
Document Type
Article
Personal Identifier
scopus
DOI Link
https://doi.org/10.13001/1081-3810.3675
Copyright Status
Unknown
Socpus ID
85055340847 (Scopus)
Source API URL
https://api.elsevier.com/content/abstract/scopus_id/85055340847
STARS Citation
Abiad, Aida; Brimkov, Boris; Martínez-Rivera, Xavier; Suil, O.; and Zhang, Jingmei, "Spectral Bounds For The Connectivity Of Regular Graphs With Given Order" (2018). Scopus Export 2015-2019. 9760.
https://stars.library.ucf.edu/scopus2015/9760