Sharp spectral bounds for the edge-connectivity of a regular graph

2018/10/02 by O Suil, Jongyook Park, O, Suil +5
Computer Science · Materials Science · Mathematics · #05C40 #05C50 #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Graphene research and applications #Interconnection Networks and Systems

paper · pdf · doi:10.48550/arxiv.1810.01189

openalex publication_date 2018/10/02 · openalex created_date 2018/10/12 · openalex updated_date 2026/07/28

Abstract

Let λ₂(G) and κ'(G) be the second largest eigenvalue and the edge-connectivity of a graph G, respectively. Let d be a positive integer at least 3. For t=1 or 2, Cioaba proved sharp upper bounds for λ₂(G) in a d-regular simple graph G to guarantee that κ'(G) ≥ t+1. In this paper, we settle down for all t ≥ 3.

Citations

• On graphs with equal algebraic and vertex connectivity

Related

• A best bound for λ₂(G) to guarantee κ(G) ≥ 2
• Spectral Bounds for the Connectivity of Regular Graphs with Given Order
• l-connectivity, l-edge-connectivity and spectral radius of graphs
• Spectral Threshold for Extremal Cyclic Edge-Connectivity
• Extremal Graphs for a Spectral Inequality on Edge-Disjoint Spanning Trees