Redundant Trees in Bipartite Graphs

被引：1

作者：

Hong, Yanmei ^{[1
,2
,3
]}

Wu, Yihong ^{[1
]}

Liu, Qinghai ^{[2
,3
,4
]}

机构：

[1] Fuzhou Univ, Sch Math & Stat, Fuzhou 350108, Peoples R China

[2] Fujian Sci & Technol Innovat Lab Optoelect Informa, Fuzhou 350108, Peoples R China

[3] Cybernet Fujian Univ, Key Lab Operat Res, Fuzhou 350108, Peoples R China

[4] Fuzhou Univ, Ctr Discrete Math, Fuzhou 350108, Peoples R China

来源：

MATHEMATICS | 2025年 / 13卷 / 06期

基金：

中国国家自然科学基金;

关键词：

<italic>k</italic>-connected; bipartite graphs; rooted forest;

D O I：

10.3390/math13061005

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

It has been conjectured that for each positive integer k and each tree T with bipartite (Z1,Z2), every k-connected bipartite graph G with delta(G)>= k+max{|Z1|,|Z2|} admits a subgraph T 'congruent to T such that G-V(T ') is still k-connected. In this paper, we generalize the ear decompositions of 2-connected graphs into a (k,ak)-extensible system for a general k-connected graph. As a result, we confirm the conjecture for k <= 3 by proving a slightly stronger version of it.

引用

页数：10

共 17 条

[1] CRITICALLY N-CONNECTED GRAPHS [J].

CHARTRAND, G ;

LICK, DR ;

KAUGARS, A .

PROCEEDINGS OF THE AMERICAN MATHEMATICAL SOCIETY, 1972, 32 (01) :63-+

[2]

Dirac G.A., 1952, Journal of the London Mathematical Society, V1, P85

[3] Non-separating trees in connected graphs [J].

Diwan, Ajit A. ;

Tholiya, Namrata P. .

DISCRETE MATHEMATICS, 2009, 309 (16) :5235-5237

[4] Connectivity keeping edges in graphs with large minimum degree [J].

Fujita, Shinya ;

Kawarabayashi, Ken-ichi .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 2008, 98 (04) :805-811

[5] Connectivity keeping trees in 2-connected graphs [J].

Hasunuma, Toru ;

Ono, Kosuke .

JOURNAL OF GRAPH THEORY, 2020, 94 (01) :20-29

[6] Mader's conjecture for graphs with small connectivity [J].

Hong, Yanmei ;

Liu, Qinghai .

JOURNAL OF GRAPH THEORY, 2022, 101 (03) :379-388

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

Hong, Yanmei ;

Liu, Qinghai ;

Lu, Changhong ;

Ye, Qingjie .

DISCRETE MATHEMATICS, 2021, 344 (03)

[8] Connectivity keeping trees in 3-connected or 3-edge-connected graphs [J].

Liu, Haiyang ;

Liu, Qinghai ;

Hong, Yanmei .

DISCRETE MATHEMATICS, 2023, 346 (12)

[9] Highly connected triples and Mader's conjecture [J].

Liu, Qinghai ;

Ying, Kai ;

Hong, Yanmei .

JOURNAL OF GRAPH THEORY, 2024, 107 (03) :478-484

[10] Connectivity keeping trees in 2-connected graphs [J].

Lu, Changhong ;

Zhang, Ping .

DISCRETE MATHEMATICS, 2020, 343 (02)

← 1 2 →