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

Abstract

Motivated by Mader's conjecture on connectivity keeping trees, we study trees obtained from paths by adding one pendant vertex, as well as related problems in triangle-free graphs. For an integer $m$ and $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. We prove that, for positive integers $k,m,1\le i\le m-1$, every $k$-connected graph $G$ with $\delta (G)\ge \lfloor \frac{3k}{2}\rfloor +m-1$ contains a subgraph $T\cong P_m^{+}(i)$ such that $\kappa (G-V(T))\ge k$. This confirms Mader's conjecture for all pendant extensions of paths. For highly connected triangle-free graphs, a connectivity keeping result for paths was obtained in [J. Combin. Theory Ser. B, 174 (2025), 190-206]. 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|\}+[P_m^{+}(i)\text{ is bad}]$ contains a subgraph $T\cong P_m^{+}(i)$ such that $\kappa (G-V(T))\ge k$, where we use Iverson's convention for $[P_m^{+}(i)\text{ is bad}]$. This extends the corresponding result for paths to pendant extensions of paths.

16pages, 0 figures