Connectivity keeping trees in 2-connected graphs
Connectivity keeping trees in 2-connected graphs
复制标题
DOI：
10.1002/jgt.22504
复制
发表时间：
2019-10-21
影响因子：
0.9
通讯作者：
Ono, Kosuke
中科院分区：
文献类型：
--
作者：
Hasunuma, Toru;Ono, Kosuke
马德尔[J Graph Theory 65（2010），61-69]证明了对于任意m阶树T，每个最小度至少为[3 k/2]+m-1的k-连通图G都包含一个与T全等的子树T '，使得G-V（T '）是k-连通的.本文证明了对任意m阶树T，每个最小度至少为max{m+n（T）-3，m +2}的2-连通图G都包含一个近似等于T的子树T '，使得G-V（T '）是2-连通的，其中n（T）表示T的内部顶点数.此外，当T是毛毛虫和拟单调毛毛虫时，最小度的下界可分别改进为max{m+n（T）/4+1/2+2}和m+2.由我们的结果可知，马德尔的2-连通图猜想对任意树T成立，其中n（T）
Mader [J Graph Theory 65 (2010), 61-69] conjectured that for any tree T of order m, every k-connected graph G with minimum degree at least [3k/2]+m-1 contains a subtree T ' congruent to T such that G-V(T ') is k-connected. In this paper, we show that for any tree T of order m, every 2-connected graph G with minimum degree at least max{m+n(T)-3,m+2} contains a subtree T ' approximately equal to T such that G-V(T ') is 2-connected, where n(T) denotes the number of internal vertices of T. Besides, the lower bound on the minimum degree can be improved to max{m+n(T)/4+1/2+2} and m+2 if T is a caterpillar and a quasi-monotone caterpillar, respectively. From our results, it follows that Mader's conjecture for 2-connected graphs is true for any tree T with n(T)