Spectral bounds for the connectivity of regular graphs with given order

Aida Abiad, Boris Brimkov, Xavier Martínez-Rivera, O. Suil, Jingmei Zhang

Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

12 Citaten (Scopus)


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.

Originele taal-2Engels
Pagina's (van-tot)428-443
Aantal pagina's16
TijdschriftElectronic Journal of Linear Algebra
StatusGepubliceerd - sep. 2018
Extern gepubliceerdJa


Duik in de onderzoeksthema's van 'Spectral bounds for the connectivity of regular graphs with given order'. Samen vormen ze een unieke vingerafdruk.

Citeer dit