2024/02/20 by Yuzhen Qi, Jin Yan, Qi, Yuzhen +1
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2402.12639
openalex publication_date 2024/02/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we show that for any positive integer m and k∈ [2], let G be a (2m+2k+2)-connected graph and let a1,… , am, s, t be any distinct vertices of G, there are k internally disjoint s-t paths P1, …, Pk in G such that \a1,… , am\ ∩ \bigcupki=1V (Pi) = ∅ and G- \bigcupki=1V (Pi) is 2-connected, which generalizes the result by Chen, Gould and Yu [Combinatorica 23 (2003) 185--203], and Kriesell [J. Graph Theory 36 (2001) 52--58]. The case k=1 implies that for any (2m+5)-connected graph G, any edge e ∈ E(G), and any distinct vertices a1,… , am of G-V(e), there exists a cycle C in G- \a1,… , am\ such that e∈ E(C) and G- V(C) is 2-connected, which improves the bound 10m+11 of Y. Hong, L. Kang and X. Yu in [J. Graph Theory 80 (2015) 253--267].