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.
|Number of pages||16|
|Journal||Electronic Journal of Linear Algebra|
|Publication status||Published - Sept 2018|
- Algebraic connectivity
- Regular multigraph
- Second-largest eigenvalue