Connectivity keeping caterpillars and spiders in 2-connected graphs

被引：11
|
作者：
Hong, Yanmei [1 ]
Liu, Qinghai [2 ]
Lu, Changhong [3 ]
Ye, Qingjie [3 ]
机构：
[1] Fuzhou Univ, Coll Math & Comp Sci, Fuzhou 350108, Peoples R China
[2] Fuzhou Univ, Ctr Discrete Math, Fuzhou 350002, Fujian, Peoples R China
[3] East China Normal Univ, Shanghai Key Lab PMMP, Sch Math Sci, Shanghai 200241, Peoples R China
来源：
DISCRETE MATHEMATICS | 2021年 / 344卷 / 03期
关键词：
Caterpillars; Spider; 2-connected graphs; Connectivity; Trees; TREES;
D O I：
10.1016/j.disc.2020.112236
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
Mader (2010) 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. A caterpillar is a tree in which a single path is incident to every edge. The conjecture has been proved when k = 1 and for some special caterpillars when k = 2. A spider is a tree with at most one vertex with degree more than 2. In this paper, we confirm the conjecture for all caterpillars and spiders when k = 2. Spider (C) 2020 Elsevier B.V. All rights reserved.
引用
收藏
页数：4
相关论文
共 50 条
  • [21] Reconstruction of distance hereditary 2-connected graphs
    Priya, P. Devi
    Monikandan, S.
    DISCRETE MATHEMATICS, 2018, 341 (08) : 2326 - 2331
  • [22] Contractible edges in 2-connected locally finite graphs
    Chan, Tsz Lung
    ELECTRONIC JOURNAL OF COMBINATORICS, 2015, 22 (02)
  • [23] 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
  • [24] Connectivity preserving trees in k-connected or k-edge-connected graphs
    Hasunuma, Toru
    JOURNAL OF GRAPH THEORY, 2023, 102 (03) : 423 - 435
  • [25] Proof of a conjecture on connectivity keeping odd paths in k-connected bipartite graphs ☆
    Yang, Qing
    Tian, Yingzhi
    DISCRETE MATHEMATICS, 2025, 348 (08)
  • [26] 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
  • [27] Approximation Algorithm for the Balanced 2-Connected Bipartition Problem
    Wu, Di
    Zhang, Zhao
    Wu, Weili
    Huang, Xiaohui
    COMPUTING AND COMBINATORICS, COCOON 2014, 2014, 8591 : 441 - 452
  • [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] Minimal Extremal Graphs for Addition of Algebraic Connectivity and Independence Number of Connected Graphs
    Das, Kinkar Ch.
    Liu, Muhuo
    FILOMAT, 2017, 31 (18) : 5545 - 5551
12345