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 条
  • [11] Connectivity preserving trees in k-connected or k-edge-connected graphs
    Hasunuma, Toru
    JOURNAL OF GRAPH THEORY, 2023, 102 (03) : 423 - 435
  • [12] Connectivity Keeping Trees in 2-Connected Graphs with Girth Conditions
    Hasunuma, Toru
    ALGORITHMICA, 2021, 83 (09) : 2697 - 2718
  • [13] Rainbow Connection in 3-Connected Graphs
    Xueliang Li
    Yongtang Shi
    Graphs and Combinatorics, 2013, 29 : 1471 - 1475
  • [14] Rainbow Connection in 3-Connected Graphs
    Li, Xueliang
    Shi, Yongtang
    GRAPHS AND COMBINATORICS, 2013, 29 (05) : 1471 - 1475
  • [15] Canonical decompositions of 3-connected graphs
    Carmesin, Johannes
    Kurkofka, Jan
    2023 IEEE 64TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, FOCS, 2023, : 1887 - 1920
  • [16] Spanning 3-connected index of graphs
    Xiong, Wei
    Zhang, Zhao
    Lai, Hong-Jian
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2014, 27 (01) : 199 - 208
  • [17] Vertex suppression in 3-connected graphs
    Kriesell, Matthias
    JOURNAL OF GRAPH THEORY, 2008, 57 (01) : 41 - 54
  • [18] Generation of 3-connected, planar line graphs
    Hollowbread-Smith, Phoebe
    Maffucci, Riccardo W.
    DISCRETE MATHEMATICS, 2025, 348 (02)
  • [19] On the number of contractible triples in 3-connected graphs
    Kriesell, Matthias
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2008, 98 (01) : 136 - 145
  • [20] On the hamiltonian property hierarchy of 3-connected planar graphs
    Lo, On-Hei Solomon
    ELECTRONIC JOURNAL OF COMBINATORICS, 2022, 29 (04)
12345