2023/12/10 by Qing Yang, Yang, Qing, Yingzhi Tian +1
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2312.05886
openalex publication_date 2023/12/10 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Mader [J. Combin. Theory Ser. B 40 (1986) 152-158] proved that every k-edge-connected graph G with minimum degree at least k+1 contains a vertex u such that G-\u\ is still k-edge-connected. In this paper, we prove that every k-edge-connected graph G with minimum degree at least k+2 contains an edge uv such that G-\u,v\ is k-edge-connected for any positive integer k. In addition, we show that for any tree T of order m, every k-edge-connected graph G with minimum degree greater than 4(k+m)2 contains a subtree T' isomorphic to T such that G-V(T') is k-edge-connected.