Sharp minimum degree conditions for the existence of disjoint theta graphs

被引:0
|
作者
Marshall, Emily [1 ]
Santana, Michael [2 ]
机构
[1] Arcadia Univ, Dept Comp Sci & Math, Glenside, PA 19038 USA
[2] Grand Valley State Univ, Dept Math, Allendale, MI 49401 USA
关键词
CHORDED CYCLES;
D O I
10.37236/9670
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
In 1963, Corradi and Hajnal showed that if G is an n-vertex graph with n >= 3k and delta(G) >= 2k, then G will contain k disjoint cycles; furthermore, this result is best possible, both in terms of the number of vertices as well as the minimum degree. In this paper we focus on an analogue of this result for theta graphs. Results from Kawarabayashi and Chiba et al. showed that if n = 4k and delta(G) > leftperpendicular5/2 krightperpendicular, or if n is large with respect to k and delta(G) >= 2k + 1, respectively, then G contains k disjoint theta graphs. While the minimum degree condition in both results are sharp for the number of vertices considered, this leaves a gap in which no sufficient minimum degree condition is known. Our main result in this paper resolves this by showing if n >= 4k and delta(G) >= leftperpendicular5/2 krightperpendicular, then G contains k disjoint theta graphs. Furthermore, we show this minimum degree condition is sharp for more than just n = 4k, and we discuss how and when the sharp minimum degree condition may transition from leftperpendicular5/2 krightperpendicular to 2k + 1.
引用
收藏
页数:25
相关论文
共 4 条
  • [1] Sharp minimum degree conditions for disjoint doubly chorded cycles
    Santana, Michael
    VAN Bonn, Maia
    JOURNAL OF COMBINATORICS, 2024, 15 (02) : 217 - 282
  • [2] 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
  • [3] 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
  • [4] Disjoint cycles and chorded cycles in a graph with given minimum degree
    Molla, Theodore
    Santana, Michael
    Yeager, Elyse
    DISCRETE MATHEMATICS, 2020, 343 (06)