Removal paths avoiding vertices

Abstract

In this paper, we show that for any positive integer $m$ and $k\in [2]$, let $G$ be a $(2m+2k+2)$-connected graph and let $a_1,\dots ,a_m,s,t$ be any distinct vertices of $G$, there are $k$ internally disjoint $s$-$t$ paths $P_1,\dots ,P_k$ in $G$ such that $\{a_1,\dots ,a_m\}\cap {\bigcup }_{i=1}^{k}V(P_i)=\varnothing$ and $G-{\bigcup }_{i=1}^{k}V(P_i)$ 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\in E(G)$, and any distinct vertices $a_1,\dots ,a_m$ of $G-V(e)$, there exists a cycle $C$ in $G-\{a_1,\dots ,a_m\}$ such that $e\in 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].

arXiv comment10 pages