Connectivity keeping trees in 3-connected or 3-edge-connected graphs

被引：2
|
作者：
Liu, Haiyang [1 ]
Liu, Qinghai [1 ,2 ,4 ]
Hong, Yanmei [3 ,4 ]
机构：
[1] Fuzhou Univ, Ctr Discrete Math, Fuzhou 350108, Fujian, Peoples R China
[2] Fujian Sci & Technol Innovat Lab Optoelect Informa, Fuzhou 350100, Peoples R China
[3] Fuzhou Univ, Sch Math & Stat, Fuzhou 350108, Fujian, Peoples R China
[4] Ctr Appl Math Fujian Provincen, Fuzhou 350108, Peoples R China
来源：
DISCRETE MATHEMATICS | 2023年 / 346卷 / 12期
关键词：
Connectivity; Subdivision; Trees;
D O I：
10.1016/j.disc.2023.113679
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
Hasunuma conjectured that for any tree of order m and for any k-connected (resp. k-edge-connected) graph G, if delta(G)>= k+m-1 then G contains a subgraph H congruent to T such that G-E(H) is k-connected (resp. k-edge-connected). Hasunuma verified the conjecture for k=1,2. In this paper, we confirm the conjecture when k=3.
引用
收藏
页数：4
相关论文
共 50 条
  • [1] Connectivity keeping edges of trees in 3-connected or 3-edge-connected graphs
    Yang, Qing
    Tian, Yingzhi
    DISCRETE MATHEMATICS, 2024, 347 (05)
  • [2] Circumference of 3-connected claw-free graphs and large Eulerian subgraphs of 3-edge-connected graphs
    Bilinski, Mark
    Jackson, Bill
    Ma, Jie
    Yu, Xingxing
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2011, 101 (04) : 214 - 236
  • [3] A synthesis for uniformly 3-edge-connected graphs
    Kingsford, Carl
    Marcais, Guillaume
    DISCRETE APPLIED MATHEMATICS, 2025, 368 : 18 - 29
  • [4] Edge number of 3-connected diameter 3 graphs
    Tsai, MC
    Fu, HL
    I-SPAN 2004: 7TH INTERNATIONAL SYMPOSIUM ON PARALLEL ARCHITECTURES, ALGORITHMS AND NETWORKS, PROCEEDINGS, 2004, : 364 - 367
  • [5] Connectivity keeping trees in 2-connected graphs
    Hasunuma, Toru
    Ono, Kosuke
    JOURNAL OF GRAPH THEORY, 2020, 94 (01) : 20 - 29
  • [6] Connectivity Keeping Trees in k-Connected Graphs
    Mader, W.
    JOURNAL OF GRAPH THEORY, 2012, 69 (04) : 324 - 329
  • [7] Connectivity keeping trees in 2-connected graphs
    Lu, Changhong
    Zhang, Ping
    DISCRETE MATHEMATICS, 2020, 343 (02)
  • [8] Connectivity Keeping Trees in k-Connected Graphs
    Mader, W.
    JOURNAL OF GRAPH THEORY, 2012, 69 (03) : 324 - 329
  • [9] Connectivity Keeping Trees in 2-Connected Graphs with Girth Conditions
    Hasunuma, Toru
    COMBINATORIAL ALGORITHMS, IWOCA 2020, 2020, 12126 : 316 - 329
  • [10] Connectivity Keeping Trees in 2-Connected Graphs with Girth Conditions
    Toru Hasunuma
    Algorithmica, 2021, 83 : 2697 - 2718
12345