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≤ i≤ m−1, let Pm+(i) denote the tree obtained from a path of order m−1 by adding one pendant vertex adjacent to its ith vertex. We prove that, for positive integers k,m,1≤ i≤ m−1, every k-connected graph G with δ(G)≥ ⌊ 3k/2⌋+m−1 contains a subgraph T≅ Pm+(i) such that κ(G−V(T))≥ 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 Pm+(i). We further prove that every k-connected triangle-free graph G with δ(G)≥ k+max{|X|,|Y|}+[Pm+(i) is bad] contains a subgraph T≅ Pm+(i) such that κ(G−V(T))≥ k, where we use Iverson's convention for [Pm+(i) is bad]. This extends the corresponding result for paths to pendant extensions of paths.
Related
- Connectivity keeping pendant extensions of paths in k-connected triangle-free graphs
- Bounds for the Vertex Chromatic Number of Connected Triangle-Free Graphs
- Eccentric Connectivity Index of Cartesian product and Strong product of Strongly Connected Digraphs
- Sharp connectivity thresholds for mixed rigidity packings and improved bounds for highly connected orientations of graphs
- Reversing the Mostar line-graph inequality with long pendant paths
BibTeX
@misc{ma2026connectivity,
title = {{Connectivity keeping pendant extensions of paths in $k$-connected graphs and triangle-free graphs}},
author = {Menghan Ma and Qinghai Liu and Liping Zhang and Yanmei Hong},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.23634},
eprint = {2609.23634},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.23634},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Connectivity keeping pendant extensions of paths in k-connected graphs and triangle-free graphs
AU - Menghan Ma
AU - Qinghai Liu
AU - Liping Zhang
AU - Yanmei Hong
PY - 2026
DA - 2026/09/20
PB - arXiv
DO - 10.48550/arxiv.2609.23634
UR - https://arxiv.org/abs/2609.23634
AB - 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≤ 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. We prove that, for positive integers k,m,1≤ i≤ m−1, every k-connected graph G with δ(G)≥ ⌊ 3k/2⌋+m−1 contains a subgraph T≅ P_m^+(i) such that κ(G−V(T))≥ 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 δ(G)≥ k+max{|X|,|Y|}+[P_m^+(i) is bad] contains a subgraph T≅ P_m^+(i) such that κ(G−V(T))≥ k, where we use Iverson's convention for [P_m^+(i) is bad]. This extends the corresponding result for paths to pendant extensions of paths.
ER -