Sharp minimum degree conditions for the existence of disjoint theta graphs
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\).
scientific article; zbMATH DE number 7402029
scientific article