A degree sum condition for the existence of a quasi 5-contractible edge in a quasi 5-connected graph

2025/09/30 by Kou, Shuai, Qin, Chengfu, Yang, Weihua +2
#05C40 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2509.25809

Abstract

An edge of a quasi k-connected graph is said to be quasi k-contractible if the contraction of the edge results in a quasi k-connected graph. We show that every 5-connected graph contains a quasi 5-contractible edge. Furthermore, we prove that a quasi 5-connected graph possesses a quasi 5-contractible edge, if the degree sum of any two vertices with distance at most two is at least 9. This result strengthens a theorem proved by Kriesell when k=4 (M. Kriesell, A degree sum condition for the existence of a contractible edge in a k-connected graph, J. Combin. Theory Ser. B 82(2001)81-101).

Related

• A forbidden pair for quasi 5-contractible edges
• Contractible Subgraphs of Contraction Critically Quasi 5-Connected Graphs
• A Note on Contractible Edges in Chordal Graphs
• Contractible Non-Edges in 3-Connected Graphs
• Construction Sequences and Certifying 3-Connectedness