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 条
  • [31] Connectivity Preserving Hamiltonian Cycles in k-Connected Dirac GraphsConnectivity Preserving Hamiltonian Cycles in k-Connected Dirac GraphsT. Hasunuma
    Toru Hasunuma
    Graphs and Combinatorics, 2025, 41 (1)
  • [32] Rainbow k-connectivity of Random Bipartite Graphs
    Xiao-lin Chen
    Xue-liang Li
    Hui-shu Lian
    Acta Mathematicae Applicatae Sinica, English Series, 2020, 36 : 879 - 890
  • [33] The k-Restricted Edge Connectivity of Balanced Bipartite Graphs
    Jun Yuan
    Aixia Liu
    Graphs and Combinatorics, 2011, 27 : 289 - 303
  • [34] The k-Restricted Edge Connectivity of Balanced Bipartite Graphs
    Yuan, Jun
    Liu, Aixia
    GRAPHS AND COMBINATORICS, 2011, 27 (02) : 289 - 303
  • [35] Hamiltonian and long cycles in bipartite graphs with connectivity
    Gan, Zhiyong
    Xu, Yanping
    DISCRETE APPLIED MATHEMATICS, 2021, 301 : 49 - 64
  • [36] A LINEAR-TIME ALGORITHM FOR FINDING A SPARSE K-CONNECTED SPANNING SUBGRAPH OF A K-CONNECTED GRAPH
    NAGAMOCHI, H
    IBARAKI, T
    ALGORITHMICA, 1992, 7 (5-6) : 583 - 596
  • [37] On the Structure of Contractible Edges in k-connected Partial k-trees
    N. S. Narayanaswamy
    N. Sadagopan
    L. Sunil Chandran
    Graphs and Combinatorics, 2009, 25 : 557 - 569
  • [38] Super connectivity of Kronecker product of complete bipartite graphs and complete graphs
    Ekinci, Gulnaz Boruzanli
    Kirlangic, Alpay
    DISCRETE MATHEMATICS, 2016, 339 (07) : 1950 - 1953
  • [39] Finding densest k-connected subgraphs
    Bonchi, Francesco
    Garcia-Soriano, David
    Miyauchi, Atsushi
    Tsourakakis, Charalampos E.
    DISCRETE APPLIED MATHEMATICS, 2021, 305 : 34 - 47
  • [40] Accessibility and Reliability for Connected Bipartite Graphs
    Y. Ath
    M. Ebneshahrashoob
    T. Gao
    M. Sobel
    Methodology And Computing In Applied Probability, 2002, 4 (2) : 153 - 161
12345