Connectivity keeping trees in triangle-free graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911257334906880 |
|---|---|
| author | Chu, Hojin Fujita, Shinya Park, Boram Ryu, Homoon |
| author_facet | Chu, Hojin Fujita, Shinya Park, Boram Ryu, Homoon |
| contents | In 2012, Mader conjectured that for any tree $T$ of order $m$, every $k$-connected graph $G$ with minimum degree at least $\lfloor \frac{3k}{2}\rfloor+m-1$ contains a subtree $T'\cong T$ such that $G-V(T')$ remains $k$-connected. In 2022, Luo, Tian, and Wu considered an analogous problem for bipartite graphs and conjectured that for any tree $T$ with bipartition $(X,Y)$, every $k$-connected bipartite graph $G$ with minimum degree at least $k+\max\{|X|,|Y|\}$ contains a subtree $T'\cong T$ such that $G-V(T')$ remains $k$-connected. In this paper, we relax the bipartite assumption by considering triangle-free graphs and prove that for any tree $T$ of order $m$, every $k$-connected triangle-free graph $G$ with minimum degree at least $2k+3m-4$ contains a subtree $T' \cong T$ such that $G-V(T')$ remains $k$-connected. Furthermore, we establish refined results for specific subclasses such as bipartite graphs or graphs with girth at least five. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_06622 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Connectivity keeping trees in triangle-free graphs Chu, Hojin Fujita, Shinya Park, Boram Ryu, Homoon Combinatorics In 2012, Mader conjectured that for any tree $T$ of order $m$, every $k$-connected graph $G$ with minimum degree at least $\lfloor \frac{3k}{2}\rfloor+m-1$ contains a subtree $T'\cong T$ such that $G-V(T')$ remains $k$-connected. In 2022, Luo, Tian, and Wu considered an analogous problem for bipartite graphs and conjectured that for any tree $T$ with bipartition $(X,Y)$, every $k$-connected bipartite graph $G$ with minimum degree at least $k+\max\{|X|,|Y|\}$ contains a subtree $T'\cong T$ such that $G-V(T')$ remains $k$-connected. In this paper, we relax the bipartite assumption by considering triangle-free graphs and prove that for any tree $T$ of order $m$, every $k$-connected triangle-free graph $G$ with minimum degree at least $2k+3m-4$ contains a subtree $T' \cong T$ such that $G-V(T')$ remains $k$-connected. Furthermore, we establish refined results for specific subclasses such as bipartite graphs or graphs with girth at least five. |
| title | Connectivity keeping trees in triangle-free graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2511.06622 |