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 条

[41] Spanning k-Ended Tree in 2-Connected Graph
Lei, Wanpeng
Yin, Jun
AXIOMS, 2023, 12 (05)
[42] On(2, k)-connected graphs
de Gevigney, Olivier Durand
Szigeti, Zoltan
JOURNAL OF GRAPH THEORY, 2019, 91 (04) : 305 - 325
[43] 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
[44] Connectivity Preserving Hamiltonian Cycles in k-Connected Dirac Graphs
Hasunuma, Toru
GRAPHS AND COMBINATORICS, 2025, 41 (01)
[45] Graphs with the second and third maximum Wiener indices over the 2-vertex connected graphs
Bessy, Stephane
Dross, Francois
Knor, Martin
Skrekovski, Riste
DISCRETE APPLIED MATHEMATICS, 2020, 284 : 195 - 200
[46] 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,
[47] On minimally 2-(edge)-connected graphs with extremal spectral radius
Chen, Xiaodan
Guo, Litao
DISCRETE MATHEMATICS, 2019, 342 (07) : 2092 - 2099
[48] On the connectivity of infinite graphs and 2-complexes
Ayala, R
Chavez, MJ
Marquez, A
Quintero, A
DISCRETE MATHEMATICS, 1999, 194 (1-3) : 13 - 37
[49] 2-vertex connectivity in directed graphs
Georgiadis, Loukas
Italiano, Giuseppe F.
Laura, Luigi
Parotsidis, Nikos
INFORMATION AND COMPUTATION, 2018, 261 : 248 - 264
[50] On (2, k)-Hamilton-connected graphs
Dai, Tianjiao
Li, Hao
Ouyang, Qiancheng
Tian, Zengxian
DISCRETE APPLIED MATHEMATICS, 2024, 343 : 288 - 299

← 1 2 3 4 5 →