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

@misc{ma2026connectivity,
  title = {{Connectivity keeping pendant extensions of paths in $k$-connected triangle-free graphs}},
  author = {Menghan Ma and Qinghai Liu and Liping Zhang and Yanmei Hong},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.20101},
  eprint = {2610.20101},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.20101},
}

TY  - UNPB
TI  - Connectivity keeping pendant extensions of paths in k-connected triangle-free graphs
AU  - Menghan Ma
AU  - Qinghai Liu
AU  - Liping Zhang
AU  - Yanmei Hong
PY  - 2026
DA  - 2026/10/14
PB  - arXiv
DO  - 10.48550/arxiv.2610.20101
UR  - https://arxiv.org/abs/2610.20101
AB  - 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 $δ(G)\geq k+\left \lceil \frac{m}{2} \right \rceil $ contains a path P of order m such that G−V(P) remains k-connected. Moreover, if κ(G)=k, then for every end F of G and every vertex v∈ F, the path P can be chosen in G[F] with v as an endvertex. If κ(G)≥ 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≤ i≤ 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 ith vertex. Let (X,Y) be the bipartition of P_m^+(i). We further prove that every k-connected triangle-free graph G with δ(G)≥ k+max{|X|,|Y|} contains a subgraph T≅ 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.
ER  -