Edge-connectivity in regular multigraphs from eigenvalues

DOI10.1016/J.LAA.2014.09.015MaRDI QIDQ5962474zbMATH OpenOpenAlexFDO

Authors Suil O

Publication date 12 February 2016

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1409.6065

zbMATH Keywords

edge-connectivityregular multigraphssecond largest eigenvalue

Mathematics Subject Classification ID

Connectivity (05C40) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Abstract: Let $G$ be a $d$-regular multigraph, and let $lambd{a}_2(G)$ be the second largest eigenvalue of $G$. In this paper, we prove that if $lambd{a}_2(G)<fracd-1+sqrt9d^2-10d+174$, then $G$ is 2-edge-connected. Furthermore, for $tge2$ we show that $G$ is $(t+1)$-edge-connected when $lambd{a}_2(G)<d-t$, and in fact when $lambd{a}_2(G)<d-t+1$ if $t$ is odd.

Recommendations

• Eigenvalues and edge-connectivity of regular graphs
• The second largest eigenvalue and vertex-connectivity of regular multigraphs
• Sharp spectral bounds for the edge-connectivity of regular graphs
• Edge-connectivity, eigenvalues, and matchings in regular graphs
• Sharp spectral bounds for the vertex-connectivity of regular graphs

Cites work

• Eigenvalues and edge-connectivity of regular graphs
• scientific article; zbMATH DE number 1600999 (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
• On graphs with equal algebraic and vertex connectivity
• Pseudo-random graphs

Cited in

(15)

• Eigenvalues and edge-connectivity of regular graphs
• Extremal problems on saturation for the family of k-edge-connected graphs
• The effect on eigenvalues of connected graphs by adding edges
• Vertex-connectivity and eigenvalues of graphs with fixed girth
• The second largest eigenvalue and vertex-connectivity of regular multigraphs
• Connectivity and eigenvalues of graphs with given girth or clique number
• Vertex-connectivity and eigenvalues of graphs
• Sharp spectral bounds for the vertex-connectivity of regular graphs
• Sharp spectral bounds for the edge-connectivity of regular graphs
• Edge-connectivity, eigenvalues, and matchings in regular graphs
• Spectral bounds for the connectivity of regular graphs with given order
• scientific article; zbMATH DE number 2097434 (Why is no real title available?)
• Multiple edges in M. Kontsevich's graph complexes and computations of the dimensions and Euler characteristics
• The vertex connectivity and the third largest eigenvalue in regular (multi-)graphs
• Spectral conditions for edge connectivity and packing spanning trees in multigraphs

This page was built for publication: Edge-connectivity in regular multigraphs from eigenvalues

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5962474)