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
相关论文
共 50 条
  • [11] 2-connected graphs with small 2-connected dominating sets
    Caro, Y
    Yuster, R
    DISCRETE MATHEMATICS, 2003, 269 (1-3) : 265 - 271
  • [12] 2-Connected graphs with minimum general sum-connectivity index
    Tomescu, Ioan
    DISCRETE APPLIED MATHEMATICS, 2014, 178 : 135 - 141
  • [13] Pruning 2-Connected Graphs
    Chekuri, Chandra
    Korula, Nitish
    ALGORITHMICA, 2012, 62 (1-2) : 436 - 463
  • [14] Connectivity keeping paths in k-connected bipartite graphs
    Luo, Lian
    Tian, Yingzhi
    Wu, Liyun
    DISCRETE MATHEMATICS, 2022, 345 (04)
  • [15] Connectivity keeping paths for k-connected bipartite graphs
    Ji, Meng
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2025, 17 (01)
  • [16] Strongly 2-connected orientations of graphs
    Thomassen, Carsten
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2015, 110 : 67 - 78
  • [17] 2-connected and 2-edge-connected Steinhaus graphs
    Kim, D
    Lim, D
    DISCRETE MATHEMATICS, 2002, 256 (1-2) : 257 - 265
  • [18] The rainbow connection number of 2-connected graphs
    Ekstein, Jan
    Holub, Premysl
    Kaiser, Tomas
    Koch, Maria
    Camacho, Stephan Matos
    Ryjacek, Zdenek
    Schiermeyer, Ingo
    DISCRETE MATHEMATICS, 2013, 313 (19) : 1884 - 1892
  • [19] Reconstruction of distance hereditary 2-connected graphs
    Priya, P. Devi
    Monikandan, S.
    DISCRETE MATHEMATICS, 2018, 341 (08) : 2326 - 2331
  • [20] Connectivity preserving trees in k-connected or k-edge-connected graphs
    Hasunuma, Toru
    JOURNAL OF GRAPH THEORY, 2023, 102 (03) : 423 - 435