Connectivity keeping trees in 2-connected graphs

被引:15
|
作者
Hasunuma, Toru [1 ]
Ono, Kosuke [1 ]
机构
[1] Tokushima Univ, Dept Math Sci, 2-1 Minamijosanjima, Tokushima 7708506, Japan
关键词
caterpillars; 2-connected graphs; connectivity; trees;
D O I
10.1002/jgt.22504
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
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)<= 5, any caterpillar Tc with n(Tc)=6, or any quasi-monotone caterpillar.
引用
收藏
页码:20 / 29
页数:10
相关论文
empty
未找到相关数据