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

Menghan Ma; Qinghai Liu; Liping Zhang; and Yanmei Hong

In the authors' words

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 \leq i \leq 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 \leq i \leq m - 1$ , every $k$ -connected graph $G$ with $δ (G) \geq ⌊ \frac{3 k}{2} ⌋ + m - 1$ contains a subgraph $T ≅ P_{m}^{+} (i)$ such that $κ (G - V (T)) \geq 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) \geq k + max {∣ X ∣, ∣ Y ∣} + [P_{m}^{+} (i) i s ba d]$ contains a subgraph $T ≅ P_{m}^{+} (i)$ such that $κ (G - V (T)) \geq k$ , where we use Iverson's convention for $[P_{m}^{+} (i) i s ba d]$ . This extends the corresponding result for paths to pendant extensions of paths.

Main resultThe abstract does not state a limitation.

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

In the authors' words

More on Combinatorics & discrete math that day

Circular s-choice parking functions: an exact closed formula via rotational symmetry

Single-Fragment Forensic Coding via Multidimensional Cyclically Permutable Codes

The Deterministic Broadcast Channel Revisited: A Bipartite Graph Approach

Proof of Almkvist's conjecture on the unimodality of partition polynomials

On infinite families of [Pn​]-irregular graphs

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

On infinite families of $[P_{n}]$ -irregular graphs