×

Connectivity keeping stars or double-stars in 2-connected graphs. (English) Zbl 1380.05116

Summary: W. Mader [J. Graph Theory 65, No. 1, 61–69 (2010; Zbl 1234.05145)] conjectured that for every positive integer \(k\) and every finite tree \(T\) with order \(m\), every \(k\)-connected, finite graph \(G\) with \(\delta(G) \geq \lfloor \frac{3}{2} k \rfloor + m - 1\) contains a subtree \(T^\prime\) isomorphic to \(T\) such that \(G - V(T^\prime)\) is \(k\)-connected. In the same paper, Mader proved that the conjecture is true when \(T\) is a path. A. A. Diwan and N. P. Tholiya [Discrete Math. 309, No. 16, 5235–5237 (2009; Zbl 1202.05023)] verified the conjecture when \(k = 1\). In this paper, we will prove that Mader’s conjecture is true when \(T\) is a star or double-star and \(k = 2\).

MSC:

05C40 Connectivity
05E30 Association schemes, strongly regular graphs

References:

[1] Bondy, J. A.; Murty, U. S.R., (Graph Theory. 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. 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, 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] Mader, W., Connectivity keeping paths in \(k\)-connected graphs, J. Graph Theory, 65, 61-69 (2010) · Zbl 1234.05145
[6] Mader, W., Connectivity keeping trees in \(k\)-connected graphs, J. Graph Theory, 69, 324-329 (2012) · Zbl 1242.05147
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.