共 4 条
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
相关论文