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 条
  • [21] Infinite family of 2-connected transmission irregular graphs
    Dobrynin, Andrey A.
    APPLIED MATHEMATICS AND COMPUTATION, 2019, 340 : 1 - 4
  • [22] Contractible edges in 2-connected locally finite graphs
    Chan, Tsz Lung
    ELECTRONIC JOURNAL OF COMBINATORICS, 2015, 22 (02)
  • [23] Connectivity keeping caterpillars and spiders in bipartite graphs with connectivity at most three
    Yang, Qing
    Tian, Yingzhi
    DISCRETE MATHEMATICS, 2023, 346 (01)
  • [24] On the Connectivity of Token Graphs of Trees
    Fabila-Monroy, Ruy
    Leanos, Jesus
    Laura Trujillo-Negrete, Ana
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2022, 24 (01)
  • [25] Non-contractible non-edges in 2-connected graphs
    Das, Anita
    Francis, Mathew C.
    Mathew, Rogers
    Sadagopan, N.
    INFORMATION PROCESSING LETTERS, 2010, 110 (23) : 1044 - 1048
  • [26] Proof of a conjecture on connectivity keeping odd paths in k-connected bipartite graphs ☆
    Yang, Qing
    Tian, Yingzhi
    DISCRETE MATHEMATICS, 2025, 348 (08)
  • [27] Faster Algorithms for Computing Maximal 2-Connected Subgraphs in Sparse Directed Graphs
    Chechik, Shiri
    Hansen, Thomas Dueholm
    Italiano, Giuseppe F.
    Loitzenbauer, Veronika
    Parotsidis, Nikos
    PROCEEDINGS OF THE TWENTY-EIGHTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2017, : 1900 - 1918
  • [28] High connectivity keeping sets in graphs and digraphs
    Mader, W
    DISCRETE MATHEMATICS, 2005, 302 (1-3) : 173 - 187
  • [29] A CONCEPT OF WEIGHTED CONNECTIVITY ON CONNECTED GRAPHS
    Amer, Rafael
    Gimenez, Jose Miguel
    APLIMAT 2009: 8TH INTERNATIONAL CONFERENCE, PROCEEDINGS, 2009, : 43 - 48
  • [30] The hamiltonian index of a 2-connected graph
    Xiong, Liming
    Wu, Qiuxin
    DISCRETE MATHEMATICS, 2008, 308 (24) : 6373 - 6382