Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | https://arxiv.org/abs/2304.11596 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913255427932160 |
|---|---|
| author | Yang, Qing Tian, Yingzhi |
| author_facet | Yang, Qing Tian, Yingzhi |
| contents | Luo, Tian and Wu conjectured in 2022 that for any tree $T$ with bipartition $X$ and $Y$, every $k$-connected bipartite graph $G$ with $δ(G) \geq k + t$, where $t = \max\{|X|,|Y |\}$, contains a subtree $T' \cong T$ such that $G-V(T')$ remains $k$-connected. This conjecture has been proved for caterpillars and spiders when $k\leq 3$; and for paths with odd order. In this paper, we prove that this conjecture holds if $G$ is a bipartite graph with $g(G)\geq diam(T)-1$ and $k\leq 3$, where $g(G)$ and $diam(T)$ denote the girth of $G$ and the diameter of $T$, respectively. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2304_11596 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Connectivity keeping trees in 3-connected bipartite graphs with girth conditions Yang, Qing Tian, Yingzhi Combinatorics Luo, Tian and Wu conjectured in 2022 that for any tree $T$ with bipartition $X$ and $Y$, every $k$-connected bipartite graph $G$ with $δ(G) \geq k + t$, where $t = \max\{|X|,|Y |\}$, contains a subtree $T' \cong T$ such that $G-V(T')$ remains $k$-connected. This conjecture has been proved for caterpillars and spiders when $k\leq 3$; and for paths with odd order. In this paper, we prove that this conjecture holds if $G$ is a bipartite graph with $g(G)\geq diam(T)-1$ and $k\leq 3$, where $g(G)$ and $diam(T)$ denote the girth of $G$ and the diameter of $T$, respectively. |
| title | Connectivity keeping trees in 3-connected bipartite graphs with girth conditions |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2304.11596 |