Edge-connectivity in regular multigraphs from eigenvalues

DOI10.1016/J.LAA.2014.09.015zbMATH Open1330.05106arXiv1409.6065OpenAlexW1969496240MaRDI QIDQ5962474FDOQ5962474

Authors: Suil O 

Publication date: 12 February 2016

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

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.

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

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

zbMATH Keywords

second largest eigenvalueedge-connectivityregular multigraphs

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• On graphs with equal algebraic and vertex connectivity
• Pseudo-random graphs
• Eigenvalues and edge-connectivity of regular graphs
• Minimum cuts, girth and a spectral threshold

Cited In (15)

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

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)