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 条
  • [41] On the Degree Distribution of k-Connected Random Networks
    Bettstetter, Christian
    Klinglmayr, Johannes
    Lettner, Stefan
    2010 IEEE INTERNATIONAL CONFERENCE ON COMMUNICATIONS, 2010,
  • [42] Extremal connectivity for topological cliques in bipartite graphs
    Kühn, D
    Osthus, D
    JOURNAL OF COMBINATORIAL THEORY SERIES B, 2006, 96 (01) : 73 - 99
  • [43] On Biclique Connectivity in Bipartite Graphs and Recommendation Systems
    Maier, Cristina
    Simovici, Dan
    5TH INTERNATIONAL CONFERENCE ON INFORMATION SYSTEM AND DATA MINING (ICISDM 2021), 2021, : 151 - 156
  • [44] Private computation:: k-connected versus 1-connected networks
    Blaeser, Markus
    Jakoby, Andreas
    Liskiewicz, Maciej
    Manthey, Bodo
    JOURNAL OF CRYPTOLOGY, 2006, 19 (03) : 341 - 357
  • [45] Private Computation: k-Connected versus 1-Connected Networks
    Markus Bläser
    Andreas Jakoby
    Maciej Liskiewicz
    Bodo Manthey
    Journal of Cryptology, 2006, 19 : 341 - 357
  • [46] Approximating k-Connected m-Dominating Sets
    Zeev Nutov
    Algorithmica, 2022, 84 : 1511 - 1525
  • [47] K-Connected Cores Computation in Large Dual Networks
    Cui L.
    Yue L.
    Wen D.
    Qin L.
    Data Science and Engineering, 2018, 3 (4) : 293 - 306
  • [48] Conditions for families of disjoint k-connected subgraphs in a graph
    Ferrara, Michael
    Magnant, Colton
    Wenger, Paul
    DISCRETE MATHEMATICS, 2013, 313 (06) : 760 - 764
  • [49] High connectivity keeping sets in graphs and digraphs
    Mader, W
    DISCRETE MATHEMATICS, 2005, 302 (1-3) : 173 - 187
  • [50] A CONCEPT OF WEIGHTED CONNECTIVITY ON CONNECTED GRAPHS
    Amer, Rafael
    Gimenez, Jose Miguel
    APLIMAT 2009: 8TH INTERNATIONAL CONFERENCE, PROCEEDINGS, 2009, : 43 - 48
12345