Spectral Bounds for the Connectivity of Regular Graphs with Given Order

Aida Abiad, Boris Brimkov, Xavier Martinez-Rivera, O Suil, Jingmei Zhang

Published 2017-03-08Version 1

The second-largest eigenvalue and second-smallest Laplacian eigenvalue of a graph are measures of the graph's connectivity. These parameters can be used to analyze the robustness, resilience, and synchronizability of networks, and are related to other connectivity attributes such as the vertex- and edge-connectivity, isoperimetric number, and characteristic path length. In this paper, we give upper bounds for the second-largest eigenvalues of regular graphs and multigraphs 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.