Article in press
Authors:
Title:
Non-path results on the connectivity keeping problem
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2024-08-16 , Revised: 2024-12-24 , Accepted: 2025-01-06 , Available online: 2025-02-01 , https://doi.org/10.7151/dmgt.2578
Abstract:
Fujita and Kawarabayashi conjectured that for all positive integers $k$, $m$,
there is a (least) non-negative integer $f_{k}(m)$ such that every $k$-connected
graph $G$ with $\delta(G)\geq \left\lfloor\frac{3k}{2}\right\rfloor+ f_{k}(m)-1$
contains a connected subgraph $W$ of order $m$ such that $G-V(W)$ is still
$k$-connected. Mader confirmed that Fujita-Kawarabayashi's conjecture is true
when $W$ is a path, if $f_{k}(m)=m$. Mader conjectured that for every positive
integer $k$ and finite tree $T$ of order $m$, every $k$-connected finite graph
$G$ with minimum degree $\delta(G)\geq\left\lfloor\frac{3k}{2}\right\rfloor+m-1$
contains a subgraph $T'\cong T$ such that $G-V(T')$ remains $k$-connected. Till
now, there is hardly a result on high connectivity $G$ and a non-path. Luo,
Tian and Wu proposed a stronger conjecture, that is, for any tree $T$ with
bipartition $(X,Y)$, every $k$-connected bipartite graph $G$ with $\delta(G)
\geq k+w$, where $w = \max\{|X|,|Y|\}$, contains a tree $T'\cong T$ such that
$\kappa(G-V(T'))\geq k.$
In this paper, we develop Mader's method and give a result on high connectivity
$G$ and a non-path $T$. Firstly, the author proves that for positive integers
$k\geq 1$ and $m\neq 4$ or $5$, every $k$-connected bipartite graph $G$ with
$\delta(G)\geq k+\left\lceil\frac{m+1}{2}\right\rceil$ contains a star-path
$T^{3}_{m-3}$ such that $\kappa(G-V(T^{3}_{m-3}))\geq k,$ where $T_{m-3}^{3}$
is a tree constructed by connecting one leaf of $K_{1,3}$ and one end-vertex of
a path $P$ on $m-4$ vertices. Secondly, we prove Mader's conjecture is true
when $T$ is a star-path under condition of $\Delta(G)=|G|-1$.
Keywords:
connectivity, bipartite graph, fragment, end
References:
- J.A. Bondy and U.S.R. Murty, Graph Theory, Grad. Texts in Math. 244 (Springer-Verlag, London, 2008).
https://doi.org/10.1007/978-1-84628-970-5 - G. Chartrand, A. Kaigars and D.R. Lick, Critically $n$-connected graphs, Proc. Amer. Math. Soc. 32 (1972) 63–68.
- A.A. Diwan and N.P. Tholiya, Non-separating trees in connected graphs, Discrete Math. 309 (2009) 5235–5237.
https://doi.org/10.1016/j.disc.2009.03.037 - S. Fujita and K.-i. Kawarabayashi, Connectivity keeping edges in graphs with large minimum degree, J. Combin. Theory Ser. B 98 (2008) 805–811.
https://doi.org/10.1016/j.jctb.2007.11.001 - T. Hasunuma, Connectivity keeping trees in $2$-connected graphs with girth conditions, Algorithmica 83 (2021) 2697–2718.
https://doi.org/10.1007/s00453-021-00833-8 - T. Hasunuma and K. Ono, Connectivity keeping trees in $2$-connected graphs, J. Graph Theory 94 (2020) 20–29.
https://doi.org/10.1002/jgt.22504 - Y. Hong and Q. Liu, Mader's conjecture for graphs with small connectivity, J. Graph Theory 101 (2022) 379–388.
https://doi.org/10.1002/jgt.22831 - Y. Hong, Q. Liu, C. Lu and Q. Ye, Connectivity keeping caterpillars and spiders in $2$-connected graphs, Discrete Math. 344(3) (2021) 112236.
https://doi.org/10.1016/j.disc.2020.112236 - C. Lv and P. Zhang, Connectivity keeping trees in $2$-connected graphs, Discrete Math. 343(2) (2020) 111677.
https://doi.org/10.1016/j.disc.2019.111677 - L. Luo, Y. Tian and L. Wu, Connectivity keeping paths in $k$-connected bipartite graphs, Discrete Math. 345(4) (2022) 112788.
https://doi.org/10.1016/j.disc.2021.112788 - W. Mader, Connectivity keeping paths in $k$-connected graphs, J. Graph Theory 65 (2010) 61–69.
https://doi.org/10.1002/jgt.20465 - W. Mader, Connectivity keeping trees in $k$-connected graphs, J. Graph Theory 69 (2012) 324–329.
https://doi.org/10.1002/jgt.20585 - Y. Tian, H.-J. Lai, L. Xu and J. Meng, Nonseparating trees in $2$-connected graphs and oriented trees in strongly connected digraphs, Discrete Math. 342 (2019) 344–351.
https://doi.org/10.1016/j.disc.2018.10.001 - Y. Tian, J. Meng, H.-J. Lai and L. Xu, Connectivity keeping stars or double-stars in $2$-connected graphs, Discrete Math. 341 (2018) 1120–1124.
https://doi.org/10.1016/j.disc.2017.10.017 - Q. Yang and Y. Tian, Connectivity keeping caterpillars and spiders in bipartite graphs with connectivity at most three, Discrete Math. 346(1) (2023) 113207.
https://doi.org/10.1016/j.disc.2022.113207 - Q. Yang and Y. Tian, Proof of a conjecture on connectivity keeping odd paths in k-connected bipartite graphs (2024).
arXiv: 2209.08373v2 - P. Zhang, Research on the Existence of Subgraphs Related to Connectivity, Ph.D. Dissertation (East China Normal University, 2021).
Close