Connectivity keeping paths in k-connected bipartite graphs

被引：7
|
作者：
Luo, Lian [1 ]
Tian, Yingzhi [1 ]
Wu, Liyun [1 ]
机构：
[1] Xinjiang Univ, Coll Math & Syst Sci, Urumqi 830046, Xinjiang, Peoples R China
来源：
DISCRETE MATHEMATICS | 2022年 / 345卷 / 04期
关键词：
Connectivity; Bipartite graphs; Paths; TREES;
D O I：
10.1016/j.disc.2021.112788
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
In 2010, Mader ((2010) [10]) proved that every k-connected graph G with minimum degree at least [ 3k/2 ] + m - 1 contains a path P of order m such that G - V(P) is still k-connected. In this paper, we consider similar problem for bipartite graphs, and prove that every k-connected bipartite graph G with minimum degree at least k + m contains a path P of order m such that G - V(P) is still k-connected. (c) 2021 Elsevier B.V. All rights reserved.
引用
收藏
页数：5
相关论文
共 50 条
  • [21] The Solitaire Clobber game and the correducibility of k-connected graphs
    Fujimori, Tatsuya
    Maezawa, Shun-ichi
    Okamoto, Yoshio
    DISCRETE APPLIED MATHEMATICS, 2025, 366 : 16 - 22
  • [22] Connectivity keeping trees in 3-connected or 3-edge-connected graphs
    Liu, Haiyang
    Liu, Qinghai
    Hong, Yanmei
    DISCRETE MATHEMATICS, 2023, 346 (12)
  • [23] Connectivity keeping trees in 2-connected graphs
    Lu, Changhong
    Zhang, Ping
    DISCRETE MATHEMATICS, 2020, 343 (02)
  • [24] Connectivity Keeping Trees in 2-Connected Graphs with Girth Conditions
    Hasunuma, Toru
    COMBINATORIAL ALGORITHMS, IWOCA 2020, 2020, 12126 : 316 - 329
  • [25] Connectivity Keeping Trees in 2-Connected Graphs with Girth Conditions
    Toru Hasunuma
    Algorithmica, 2021, 83 : 2697 - 2718
  • [26] Connectivity Keeping Trees in 2-Connected Graphs with Girth Conditions
    Hasunuma, Toru
    ALGORITHMICA, 2021, 83 (09) : 2697 - 2718
  • [27] On the maximum connective eccentricity index among k-connected graphs
    Hayat, Fazal
    DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2021, 13 (02)
  • [28] A note on circumferences in k-connected graphs with given independence number
    Cui, Qing
    Zhong, Lingping
    ARS COMBINATORIA, 2013, 111 : 315 - 322
  • [29] Connectivity keeping edges of trees in 3-connected or 3-edge-connected graphs
    Yang, Qing
    Tian, Yingzhi
    DISCRETE MATHEMATICS, 2024, 347 (05)
  • [30] Longest cycles in k-connected graphs with given independence number
    Suil, O.
    West, Douglas B.
    Wu, Hehui
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2011, 101 (06) : 480 - 485
12345