Sharp minimum degree conditions for the existence of disjoint theta graphs (Q820839)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Sharp minimum degree conditions for the existence of disjoint theta graphs |
scientific article |
Statements
Sharp minimum degree conditions for the existence of disjoint theta graphs (English)
0 references
28 September 2021
0 references
Summary: In [Acta Math. Acad. Sci. Hung. 14, 423--439 (1963; Zbl 0118.19001)], \textit{K. Corradi} and \textit{A. Hajnal} showed that if \(G\) is an \(n\)-vertex graph with \(n \geqslant 3k\) and \(\delta(G) \geqslant 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 \textit{K.-i. Kawarabayashi} [J. Graph Theory 39, No. 2, 111--128 (2002; Zbl 0992.05059)] and \textit{S. Chiba} et al. [Adv. Appl. Math. 54, 105--120 (2014; Zbl 1284.05209)] showed that if \(n = 4k\) and \(\delta(G) \geqslant \lceil \frac{5}{2}k \rceil \), or if \(n\) is large with respect to \(k\) and \(\delta(G) \ge 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 \geqslant 4k\) and \(\delta(G) \geqslant \lceil \frac{5}{2}k\rceil \), 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 \(\lceil \frac{5}{2}k\rceil\) to \(2k+1\).
0 references
vertex-disjoint cycles
0 references
even cycle
0 references
theta graph
0 references
minimum degree
0 references