Spectral bounds for the connectivity of regular graphs with given order
From MaRDI portal
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, we present two upper bounds 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.
Recommendations
- Sharp spectral bounds for the vertex-connectivity of regular graphs
- Sharp spectral bounds for the edge-connectivity of regular graphs
- The second largest eigenvalue and vertex-connectivity of regular multigraphs
- Eigenvalues and edge-connectivity of regular graphs
- Edge-connectivity in regular multigraphs from eigenvalues
Cites work
- A lower bound for algebraic connectivity based on the connection-graph-stability method
- Absolute algebraic connectivity of double brooms and trees
- Connectivity, toughness, spanning trees of bounded degree, and the spectrum of regular graphs.
- Data Security Equals Graph Connectivity
- Edge-connectivity in regular multigraphs from eigenvalues
- Eigenvalues and edge-connectivity of regular graphs
- Enumeration of graphs by degree sequence
- scientific article; zbMATH DE number 840688 (Why is no real title available?)
- scientific article; zbMATH DE number 3417498 (Why is no real title available?)
- Minimum cuts, girth and a spectral threshold
- Old and new results on algebraic connectivity of graphs
- On graphs with equal algebraic and vertex connectivity
- On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
- Pseudo-random graphs
- Regular multigraphs and their application to the Monte Carlo evaluation of moments of non-linear functions of Gaussian random variables
- Resilience and survivability in communication networks: strategies, principles, and survey of disciplines
- Spectra of graphs
- The six classes of trees with the largest algebraic connectivity
- The smallest values of algebraic connectivity for unicyclic graphs
Cited in
(14)- On algebraic connectivity of directed scale-free networks
- Vertex-connectivity and eigenvalues of graphs with fixed girth
- Spectral threshold for extremal cyclic edge-connectivity
- The second largest eigenvalue and vertex-connectivity of regular multigraphs
- Toughness in pseudo-random graphs
- Connectivity and eigenvalues of graphs with given girth or clique number
- Vertex-connectivity and eigenvalues of graphs
- Cospectral pairs of regular graphs with different connectivity
- Sharp spectral bounds for the vertex-connectivity of regular graphs
- Sharp spectral bounds for the edge-connectivity of regular graphs
- The vertex connectivity and the third largest eigenvalue in regular (multi-)graphs
- l-connectivity, l-edge-connectivity and spectral radius of graphs
- Essential connectivity and spectral radius of graphs
- A unified approach to the spectral radius, connectivity and edge-connectivity of graphs
This page was built for publication: Spectral bounds for the connectivity of regular graphs with given order
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4685895)
