VERTEX-DISJOINT QUADRILATERALS IN BIPARTITE GRAPHS

被引：0
|
作者：
YAN Jin LIU Guizhen (School of Mathematics & Systems Science
机构：
来源：
JournalofSystemsScienceandComplexity | 2004年 / 04期
基金：
中国国家自然科学基金;
关键词：
Graphs; bipartite graphs; quadrilaterals; cycles;
D O I：
暂无
中图分类号：
O157.5 [图论];
学科分类号：
070104 ;
摘要：
H. Wang considered the minimum degrees condition that G has large vertex-disjoint cycles in bipartite graphs. Motivated by this, we consider the small vertex-disjoint cycles in bipartite graphs in this paper. We prove the following result: Let m > 3, n > 2 and k >1 be three integers. Let G = (V1,V2;E) be a bipartite graph with | V1| = | V2| =n > 2k+1. If the minimum degreefor any cycle C of G with length 2m, then G contains k vertex-disjoint cycles of length 4. Moreover, the degrees condition is sharp.
引用
收藏
页码：532 / 537
页数：6
相关论文
共 50 条
  • [11] Degree sum condition for vertex-disjoint triangles and pentagons
    Wang, Maoqun
    Guan, Sitong
    Zhang, Bo
    DISCRETE APPLIED MATHEMATICS, 2025, 369 : 88 - 95
  • [12] Construction of vertex-disjoint paths in alternating group networks
    Zhou, Shuming
    Xiao, Wenjun
    Parhami, Behrooz
    JOURNAL OF SUPERCOMPUTING, 2010, 54 (02) : 206 - 228
  • [13] Degree Conditions for the Existence of Vertex-Disjoint Cycles and Paths: A Survey
    Chiba, Shuya
    Yamashita, Tomoki
    GRAPHS AND COMBINATORICS, 2018, 34 (01) : 1 - 83
  • [14] Degree Conditions for the Existence of Vertex-Disjoint Cycles and Paths: A Survey
    Shuya Chiba
    Tomoki Yamashita
    Graphs and Combinatorics, 2018, 34 : 1 - 83
  • [15] Triangle strings: Structures for augmentation of vertex-disjoint triangle sets
    Zhang, Zan-Bo
    Zhang, Xiaoyan
    INFORMATION PROCESSING LETTERS, 2014, 114 (08) : 450 - 456
  • [16] On the Complexity of Finding Internally Vertex-Disjoint Long Directed Paths
    Araujo, Julio
    Campos, Victor A.
    Maia, Ana Karolinna
    Sau, Ignasi
    Silva, Ana
    ALGORITHMICA, 2020, 82 (06) : 1616 - 1639
  • [17] Vertex-disjoint paths joining adjacent vertices in faulty hypercubes
    Cheng, Dongqin
    THEORETICAL COMPUTER SCIENCE, 2019, 795 : 219 - 224
  • [18] Distance spectrum, 1-factor and vertex-disjoint cycles
    Zhang, Yuke
    Lin, Huiqiu
    Liu, Qinghai
    Zheng, Jinfeng
    LINEAR ALGEBRA AND ITS APPLICATIONS, 2022, 654 (10-27) : 10 - 27
  • [19] Iterative Message Passing Algorithm for Vertex-Disjoint Shortest Paths
    Dai, Guowei
    Guo, Longkun
    Gutin, Gregory
    Zhang, Xiaoyan
    Zhang, Zan-Bo
    IEEE TRANSACTIONS ON INFORMATION THEORY, 2022, 68 (06) : 3870 - 3878
  • [20] Vertex disjoint 4-cycles in bipartite tournaments
    Balbuena, C.
    Gonzalez-Moreno, D.
    Olsen, M.
    DISCRETE MATHEMATICS, 2018, 341 (04) : 1103 - 1108
12345