Connectivity keeping caterpillars and spiders in bipartite graphs with connectivity at most three. (English) Zbl 1502.05113
Summary: A conjecture of L. Luo et al. [Discrete Math. 345, No. 4, Article ID 112788, 5 p. (2022; Zbl 1482.05173)] says that for every positive integer \(k\) and every finite tree \(T\) with bipartition \(X\) and \(Y\) (denote \(t = \max \{| X |, | Y | \}\)), every \(k\)-connected bipartite graph \(G\) with \(\delta(G) \geq k + t\) contains a subtree \(T^\prime \cong T\) such that \(\kappa(G - V( T^\prime)) \geq k\). In this paper, we confirm this conjecture for caterpillars when \(k = 3\) and spiders when \(k \leq 3\).
Citations:
Zbl 1482.05173References:
| [1] | Bondy, J. A.; Murty, U. S.R., Graph Theory, Graduate Texts in Mathematics, vol. 244 (2008), Springer: Springer Berlin · Zbl 1134.05001 |
| [2] | Chartrand, G.; Kaigars, A.; Lick, D. R., Critically n-connected graphs, Proc. Am. Math. Soc., 32, 63-68 (1972) · Zbl 0228.05118 |
| [3] | Diwan, A. A.; Tholiya, N. P., Non-separating trees in connected graphs, Discrete Math., 309, 16, 5235-5237 (2009) · Zbl 1202.05023 |
| [4] | Fujita, S.; Kawarabayashi, K., Connectivity keeping edges in graphs with large minimum degree, J. Comb. Theory, Ser. B, 98, 805-811 (2008) · Zbl 1155.05037 |
| [5] | Hasunuma, T.; Ono, K., Connectivity keeping trees in 2-connected graphs, J. Graph Theory, 94, 20-29 (2020) · Zbl 1495.05029 |
| [6] | Hasunuma, T., Connectivity keeping trees in 2-connected graphs with girth conditions, Algorithmica, 83, 2697-2718 (2021) · Zbl 1518.05095 |
| [7] | Hong, Y.; Liu, Q.; Lu, C.; Ye, Q., Connectivity keeping caterpillars and spiders in 2-connected graphs, Discrete Math., 344, 3, Article 112236 pp. (2021) · Zbl 1466.05111 |
| [8] | Hong, Y.; Liu, Q., Mader’s conjecture for graphs with small connectivity, J. Graph Theory, 101, 3, 379-388 (2022) · Zbl 1522.05252 |
| [9] | Lu, C.; Zhang, P., Connectivity keeping trees in 2-connected graphs, Discrete Math., 343, 2, 1-4 (2020) · Zbl 1429.05110 |
| [10] | Luo, L.; Tian, Y.; Wu, L., Connectivity keeping paths in k-connected bipartite graphs, Discrete Math., 345, 4, Article 112788 pp. (2022) · Zbl 1482.05173 |
| [11] | Mader, W., Connectivity keeping paths in k-connected graphs, J. Graph Theory, 65, 61-69 (2010) · Zbl 1234.05145 |
| [12] | Mader, W., Connectivity keeping trees in k-connected graphs, J. Graph Theory, 69, 324-329 (2012) · Zbl 1242.05147 |
| [13] | Tian, Y.; Meng, J.; Lai, H.; Xu, L., Connectivity keeping stars or double-stars in 2-connected graphs, Discrete Math., 341, 4, 1120-1124 (2018) · Zbl 1380.05116 |
| [14] | Tian, Y.; Lai, H.; Xu, L.; Meng, J., Nonseparating trees in 2-connected graphs and oriented trees in strongly connected digraphs, Discrete Math., 342, 2, 344-351 (2019) · Zbl 1400.05100 |
| [15] | Zhang, P., Research on the Existence of Subgraphs Related to Connectivity (2021), East China Normal University, Ph.D. dissertation |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
