Sharp minimum degree conditions for the existence of disjoint theta graphs
type: Item
instance of: scholarly article
title: Sharp minimum degree conditions for the existence of disjoint theta graphs
zbMATH Open document ID: 1473.05247
DOI: 10.37236/9670
author: Michael Santana
author: Emily A. Marshall
published in: The Electronic Journal of Combinatorics
publication date: 2021-09-28T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C07
zbMATH DE Number: 7402029
zbMATH Keywords: vertex-disjoint cycles
zbMATH Keywords: even cycle
zbMATH Keywords: theta graph
zbMATH Keywords: minimum degree
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.37236/9670
OpenAlex ID: W3199264733
cites work: Disjoint chorded cycles in graphs
cites work: Minimum degree conditions for vertex-disjoint even cycles in large graphs
cites work: On the maximal number of independent circuits in a graph
cites work: On the number of independent chorded cycles in a graph
cites work: Independet cycles and chorded cycles in graphs
cites work: K4−‐factor in a graph
cites work: Vertex-disjoint copies of K4-
cites work: Tiling Turán theorems
cites work: An Ore-type Theorem for Perfect Packings in Graphs
cites work: Disjoint cycles and chorded cycles in a graph with given minimum degree
description: scientific article; zbMATH DE number 7402029