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 条
  • [41] On connected graphs and trees with maximal inverse sum indeg index
    Chen, Xiaodan
    Li, Xiuyu
    Lin, Wenshui
    APPLIED MATHEMATICS AND COMPUTATION, 2021, 392
  • [42] On the Atom Bond Connectivity Index of Certain Trees and Unicyclic Graphs
    Mohammed, Mohanad A.
    Atan, K. A.
    Khalaf, A. M.
    Hasni, R.
    2015 INTERNATIONAL CONFERENCE ON RESEARCH AND EDUCATION IN MATHEMATICS (ICREM7), 2015, : 205 - 210
  • [43] Approximation algorithm for the balanced 2-connected k-partition problem
    Wu, Di
    Zhang, Zhao
    Wu, Weili
    THEORETICAL COMPUTER SCIENCE, 2016, 609 : 627 - 638
  • [44] On(2, k)-connected graphs
    de Gevigney, Olivier Durand
    Szigeti, Zoltan
    JOURNAL OF GRAPH THEORY, 2019, 91 (04) : 305 - 325
  • [45] Independence number and connectivity of maximal connected domination vertex critical graphs
    Almalki, Norah
    Kaemawicharnurat, Pawaton
    COMMUNICATIONS IN COMBINATORICS AND OPTIMIZATION, 2023, 9 (02) : 185 - 196
  • [46] Connectivity, toughness, spanning trees of bounded degree, and the spectrum of regular graphs
    Sebastian M. Cioabă
    Xiaofeng Gu
    Czechoslovak Mathematical Journal, 2016, 66 : 913 - 924
  • [47] Connectivity Preserving Hamiltonian Cycles in k-Connected Dirac Graphs
    Hasunuma, Toru
    GRAPHS AND COMBINATORICS, 2025, 41 (01)
  • [48] Improved Algorithm for Minimum Power 2-Connected Subgraph Problem in Wireless Sensor Networks
    Lakshmi, M. Prasanna
    Shetty, Pushparaj D.
    IEEE INDICON: 15TH IEEE INDIA COUNCIL INTERNATIONAL CONFERENCE, 2018,
  • [49] On the general sum-connectivity index of connected unicyclic graphs with k pendant vertices
    Tomescu, Ioan
    Arshad, Misbah
    DISCRETE APPLIED MATHEMATICS, 2015, 181 : 306 - 309
  • [50] On the Minimal General Sum-Connectivity Index of Connected Graphs Without Pendant Vertices
    Ali, Akbar
    Ahmed, Shahzad
    Du, Zhibin
    Gao, Wei
    Malik, Muhammad Aslam
    IEEE ACCESS, 2019, 7 : 136743 - 136751