Disjoint cycles covering specified vertices in bipartite graphs with partial degrees

被引:2
作者
Jiang, Suyun [1 ]
Yan, Jin [2 ]
机构
[1] Jianghan Univ, Sch Artificial Intelligence, Wuhan 430056, Hubei, Peoples R China
[2] Shandong Univ, Sch Math, Jinan 250100, Shandong, Peoples R China
基金
中国国家自然科学基金;
关键词
Bipartite graphs; Disjoint cycles; Covering; Partial degree; 2-FACTORS; NUMBER;
D O I
10.1016/j.amc.2022.127626
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
Let G be a balanced bipartite graph of order 2 n with bipartition (X, Y ) , and S a subset of X. Suppose that every pair of nonadjacent vertices {x,y} with x E S,y E Y satisfies dG(x) + dG (y ) >= n + 1 . We show that if | S| >= 2 k + 1 , then G contains k disjoint cycles such that each of them contains at least two vertices of S. Moreover, if | S| >= 2 k + 2 , then G contains k disjoint cycles covering S such that each of them contains at least two vertices of S. Here, the lower bounds of | S| are necessary, and for the latter result the degree condition is sharp.(c) 2022 Elsevier Inc. All rights reserved.
引用
收藏
页数:12
相关论文
共 17 条
  • [1] Cyclability and pancyclability in bipartite graphs
    Abderrezzak, ME
    Flandrin, E
    Amar, D
    [J]. DISCRETE MATHEMATICS, 2001, 236 (1-3) : 3 - 11
  • [2] CYCLES THROUGH SPECIFIED VERTICES
    BOLLOBAS, B
    BRIGHTWELL, G
    [J]. COMBINATORICA, 1993, 13 (02) : 147 - 155
  • [3] METHOD IN GRAPH THEORY
    BONDY, JA
    CHVATAL, V
    [J]. DISCRETE MATHEMATICS, 1976, 15 (02) : 111 - 135
  • [4] Degree Conditions for the Existence of Vertex-Disjoint Cycles and Paths: A Survey
    Chiba, Shuya
    Yamashita, Tomoki
    [J]. GRAPHS AND COMBINATORICS, 2018, 34 (01) : 1 - 83
  • [5] A note on degree sum conditions for 2-factors with a prescribed number of cycles in bipartite graphs
    Chiba, Shuya
    Yamashita, Tomoki
    [J]. DISCRETE MATHEMATICS, 2017, 340 (12) : 2871 - 2877
  • [6] 2-FACTORS OF BIPARTITE GRAPHS WITH ASYMMETRIC MINIMUM DEGREES
    Czygrinow, Andrzej
    Debiasio, Louis
    Kierstead, H. A.
    [J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 2010, 24 (02) : 486 - 504
  • [7] Diestel R., 2017, GRAPH THEORY, DOI [DOI 10.1007/978-3-662-53622-3, 10.1007/978-3-662-53622-3]
  • [8] Dirac G.A., 1952, P LOND MATH SOC, V2, P69, DOI [10.1112/plms/s3-2.1.69, DOI 10.1112/PLMS/S3-2.1.69]
  • [9] A look at cycles containing specified elements of a graph
    Gould, Ronald J.
    [J]. DISCRETE MATHEMATICS, 2009, 309 (21) : 6299 - 6311
  • [10] Partial Degree Conditions and Cycle Coverings in Bipartite Graphs
    Jiang, Suyun
    Yan, Jin
    [J]. GRAPHS AND COMBINATORICS, 2017, 33 (04) : 955 - 967