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 条

[21] Contractible Edges and Removable Edges in 3-Connected Graphs [J].

Xu, Liqiong ;

Guo, Xiaofeng .

GRAPHS AND COMBINATORICS, 2019, 35 (06) :1375-1385

[22] Contractible Edges and Removable Edges in 3-Connected Graphs [J].

Liqiong Xu ;

Xiaofeng Guo .

Graphs and Combinatorics, 2019, 35 :1375-1385

[23] Connectivity keeping paths in k-connected bipartite graphs [J].

Luo, Lian ;

Tian, Yingzhi ;

Wu, Liyun .

DISCRETE MATHEMATICS, 2022, 345 (04)

[24] Connectivity keeping caterpillars and spiders in 2-connected graphs [J].

Hong, Yanmei ;

Liu, Qinghai ;

Lu, Changhong ;

Ye, Qingjie .

DISCRETE MATHEMATICS, 2021, 344 (03)

[25] Connectivity keeping paths for k-connected bipartite graphs [J].

Ji, Meng .

DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2025, 17 (01)

[26] Infinite family of 3-connected cubic transmission irregular graphs [J].

Dobrynin, Andrey A. .

DISCRETE APPLIED MATHEMATICS, 2019, 257 :151-157

[27] A constructive characterization of 3-connected triangle-free graphs [J].

Kriesell, Matthias .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2007, 97 (03) :358-370

[28] A degree sum condition for longest cycles in 3-connected graphs [J].

Yamashita, Tomoki .

JOURNAL OF GRAPH THEORY, 2007, 54 (04) :277-283

[29] A nine vertex theorem for 3-connected claw-free graphs [J].

Gyori, E ;

Plummer, MD .

STUDIA SCIENTIARUM MATHEMATICARUM HUNGARICA, 2001, 38 :233-244

[30] On small contractible subgraphs in 3-connected graphs of small average degree [J].

Kriesell, Matthias .

GRAPHS AND COMBINATORICS, 2007, 23 (05) :545-557

← 1 2 3 4 5 →