×

Connectivity keeping caterpillars and spiders in 2-connected graphs. (English) Zbl 1466.05111

Let \(V(G)\) denote the vertex set of a graph \(G\). And for a subset \(X\subset V\), let \(G-X\) denote the subgraph of \(G\) obtained by deleting the elements in \(X\) from \(G\). Further suppose that \(\delta(G)\) denotes the minimum degree of \(G\). G. Chartrand et al. [Proc. Am. Math. Soc. 32, 63–68 (1972; Zbl 0228.05118)] proved the following.
Theorem. Every \(k\)-connected graph \(G\) with minimum degree \(\delta(G)\ge \lfloor{3k/2}\rfloor\) has a vertex \(x\) such that \(G-x\) remains \(k\)-connected.
In a similar vein, W. Mader [J. Graph Theory 65, No. 1, 61–69 (2010; Zbl 1234.05145)] conjectured the following.
[Conjectures 1 and 2] For every tree \(T\) with \(n\) vertices, every \(k\)-connected graph \(G\) with \(\delta(G)\ge \lfloor{3k/2} + n-1\) contains a subtree \(T^\prime\) isomorphic to \(T\) such that \(G-V(T^\prime)\) remains \(k\)-connected.
Towards this conjecture, W. Mader [ibid. 69, No. 3–4, 324–329 (2012; Zbl 1242.05147)] proved the following.
Theorem. Let \(T\) be a tree with \(n\) vertices and let \(G\) be a \(k\)-connected graph with \(\delta(G)\ge 2(k-1+n)^2+n-1\), for positive integers \(k,n\). Then there is a tree \(T^\prime\subseteq G\) isomorphic to \(T\) such that \(G-V(T^\prime)\) remains \(k\)-connected.
The current paper proved Mader’s conjecture for \(k=2\) and two particular types of trees, the so called caterpillars (trees in which a single path is incident to every edge) and spiders (trees with at most one vertex with degree more than two). That is, they proved the following.
Theorems 7 and 10. For every caterpillar or spider \(T\) with \(n\) vertices, every 2-connected graph \(G\) with \(\delta(G)\ge n +2\) contains a subtree \(T^\prime\subseteq G\) isomorphic to \(T\) such that \(G-V(T^\prime)\) remains 2-connected.

MSC:

05C40 Connectivity
Full Text: DOI

References:

[1] Bondy, J. A.; Murty, U. S.R., (GraphTheory. GraphTheory, GraduateTexts in Mathematics, vol. 244 (2008), Springer: Springer Berlin) · Zbl 1134.05001
[2] Chartrand, G.; Kaigars, A.; Lick, D. R., Critically n-connected graphs, Proc. Amer. Math. Soc., 32, 63-68 (1972) · Zbl 0211.27002
[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. Combin. Theory Ser. B, 98, 805-811 (2008) · Zbl 1155.05037
[5] Hssunuma, T.; Ono, K., Connectivity keeping trees in 2-connected graphs, J. Graph Theory, 1-10 (2019)
[6] Lu, C.; Zhang, P., Connectivity keeping trees in 2-connected graphs, Discrete Math., 343, 2, 1-4 (2020) · Zbl 1429.05110
[7] Mader, W., Connectivity keeping paths in \(k\)-connected graphs, J. Graph Theory, 65, 61-69 (2010) · Zbl 1234.05145
[8] Mader, W., Connectivity keeping trees in \(k\)-connected graphs, J. Graph Theory, 69, 324-329 (2012) · Zbl 1242.05147
[9] 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
[10] 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
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.