Sharp minimum degree conditions for disjoint doubly chorded cycles

被引:0
|
作者
Santana, Michael [1 ]
VAN Bonn, Maia [2 ]
机构
[1] Grand Valley State Univ, Allendale, MI 49401 USA
[2] Univ Nebraksa Lincoln, Lincoln, NE USA
关键词
Cycles; chorded cycles; doubly chorded cycles; minimum degree;
D O I
暂无
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
In 1963, Corradi and Hajnal proved that if G is an n -vertex graph where n >= 3 k and delta ( G ) >= 2 k , then G contains k vertex -disjoint cycles, and furthermore, the minimum degree condition is best possible for all n and k where n >= 3 k . This serves as the motivation behind many results regarding best possible conditions that guarantee the existence of a fixed number of disjoint structures in graphs. For doubly chorded cycles, Qiao and Zhang proved that if n >= 4 k and delta ( G ) >= [ 7k /2 ], then G contains k vertex -disjoint doubly chorded cycles. However, the minimum degree in this result is sharp for only a finite number of values of k . Later, Gould Hirohata, and Horn improved upon this by showing that if n >= 6 k and delta ( G ) > 3 k , then G contains k vertex -disjoint doubly chorded cycles. Furthermore, this minimum degree condition is best possible for all n and k where n >= 6 k . In this paper, we prove two results. First, we extend the result of Gould et al. by showing their minimum degree condition guarantees k disjoint doubly chorded cycles even when n >= 5 k , and in addition, this is best possible for all n and k where n >= 5 k . Second, we improve upon the result of Qiao and Zhang by showing that every n -vertex graph G with n >= 4 k and delta ( G ) >= [10 k - 1/3] , contains k vertex -disjoint doubly chorded cycles. Moreover, this minimum degree is best possible for all k E Z (+) .
引用
收藏
页码:217 / 282
页数:66
相关论文
共 38 条
  • [1] Disjoint cycles and chorded cycles in a graph with given minimum degree
    Molla, Theodore
    Santana, Michael
    Yeager, Elyse
    DISCRETE MATHEMATICS, 2020, 343 (06)
  • [2] DISJOINT CHORDED CYCLES OF THE SAME LENGTH
    Chen, Guantao
    Gould, Ronald J.
    Hirohata, Kazuhide
    Ota, Katsuhiro
    Shan, Songling
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2015, 29 (02) : 1030 - 1041
  • [3] Sharp minimum degree conditions for the existence of disjoint theta graphs
    Marshall, Emily
    Santana, Michael
    ELECTRONIC JOURNAL OF COMBINATORICS, 2021, 28 (03)
  • [4] Disjoint chorded cycles in graphs
    Bialostocki, Arie
    Finkel, Daniel
    Gyarfas, Andras
    DISCRETE MATHEMATICS, 2008, 308 (23) : 5886 - 5890
  • [5] Minimum degree conditions for vertex-disjoint even cycles in large graphs
    Chiba, Shuya
    Fujita, Shinya
    Kawarabayashi, Ken-ichi
    Sakuma, Tadashi
    ADVANCES IN APPLIED MATHEMATICS, 2014, 54 : 105 - 120
  • [6] A Refinement of Theorems on Vertex-Disjoint Chorded Cycles
    Molla, Theodore
    Santana, Michael
    Yeager, Elyse
    GRAPHS AND COMBINATORICS, 2017, 33 (01) : 181 - 201
  • [7] A Refinement of Theorems on Vertex-Disjoint Chorded Cycles
    Theodore Molla
    Michael Santana
    Elyse Yeager
    Graphs and Combinatorics, 2017, 33 : 181 - 201
  • [8] Vertex-disjoint chorded cycles in a graph
    Qiao, Shengning
    Zhang, Shenggui
    OPERATIONS RESEARCH LETTERS, 2010, 38 (06) : 564 - 566
  • [9] Spanning Cyclic Subdivisions of Vertex-Disjoint Cycles and Chorded Cycles in Graphs
    Shengning Qiao
    Shenggui Zhang
    Graphs and Combinatorics, 2012, 28 : 277 - 285
  • [10] 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