Connectivity keeping pendant extensions of paths in $k$-connected triangle-free graphs

Abstract

Motivated by Mader's conjecture on connectivity keeping trees, we study the corresponding problem in triangle-free graphs. For positive integers $k,m$, we first prove that every $k$-connected triangle-free graph $G$ with $\delta (G)\ge k+\lceil \frac{m}{2}\rceil$ contains a path $P$ of order $m$ such that $G-V(P)$ remains $k$-connected. Moreover, if $\kappa (G)=k$, then for every end $F$ of $G$ and every vertex $v\in F$, the path $P$ can be chosen in $G[F]$ with $v$ as an endvertex. If $\kappa (G)\ge k+1$, then any vertex of $G$ can be chosen as an endvertex of $P$. This result confirms the conjecture of Luo, Tian and Wu on connectivity keeping trees in bipartite graphs for all paths, and it also sharpens Fujita's path theorem to the optimal minimum degree bound. For an integer $i$ with $1\le i\le m-1$, let $P_m^{+}(i)$ denote the tree obtained from a path of order $m-1$ by adding one pendant vertex adjacent to its $i$th vertex. Let $(X,Y)$ be the bipartition of $P_m^{+}(i)$. We further prove that every $k$-connected triangle-free graph $G$ with $\delta (G)\ge k+\max \{|X|,|Y|\}$ contains a subgraph $T\cong P_m^{+}(i)$ such that $G-V(T)$ remains $k$-connected. The minimum degree bound is sharp, and the result confirms the bipartite conjecture for all pendant extensions of paths.

arXiv comment14 pages