共 50 条
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
相关论文