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 条
  • [21] Monochromatic cycles in 2-edge-colored bipartite graphs with large minimum degree
    Zhang, Yiran
    Peng, Yuejian
    DISCRETE MATHEMATICS, 2025, 348 (04)
  • [22] Disjoint K 4 - in claw-free graphs with minimum degree at least five
    Gao, Yunshu
    Zou, Qingsong
    FRONTIERS OF MATHEMATICS IN CHINA, 2015, 10 (01) : 53 - 68
  • [23] MAXIMUM AND MINIMUM DEGREE CONDITIONS FOR EMBEDDING TREES
    Besomi, Guido
    Pavez-Signe, Matias
    Stein, Maya
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2020, 34 (04) : 2108 - 2123
  • [24] Minimum degree conditions for the strength and bandwidth of graphs
    Ichishima, Rikio
    Muntaner-Batle, Francesc A.
    Oshima, Akito
    DISCRETE APPLIED MATHEMATICS, 2022, 320 : 191 - 198
  • [25] Long monochromatic even cycles in 3-edge-coloured graphs of large minimum degree
    Luczak, Tomasz
    Rahimi, Zahra
    JOURNAL OF GRAPH THEORY, 2022, 99 (04) : 691 - 714
  • [26] Disjoint K4− in claw-free graphs with minimum degree at least five
    Yunshu Gao
    Qingsong Zou
    Frontiers of Mathematics in China, 2015, 10 : 53 - 68
  • [27] Spectral conditions for graphs to be β-deficient involving minimum degree
    Liu, Weijun
    Liu, Minmin
    Feng, Lihua
    LINEAR & MULTILINEAR ALGEBRA, 2018, 66 (04) : 792 - 802
  • [28] Minimum Degree Conditions for the Proper Connection Number of Graphs
    Christoph Brause
    Trung Duy Doan
    Ingo Schiermeyer
    Graphs and Combinatorics, 2017, 33 : 833 - 843
  • [29] Minimum Degree Conditions for the Proper Connection Number of Graphs
    Brause, Christoph
    Trung Duy Doan
    Schiermeyer, Ingo
    GRAPHS AND COMBINATORICS, 2017, 33 (04) : 833 - 843
  • [30] Sufficient conditions on the existence of factors in graphs involving minimum degree
    Jia, Huicai
    Lou, Jing
    CZECHOSLOVAK MATHEMATICAL JOURNAL, 2024, 74 (04) : 1299 - 1311