Sharp minimum degree conditions for disjoint doubly chorded cycles

In 1963, Corrádi and Hajnal proved that if $G$ is an $n$-vertex graph where $n \geq 3k$ and $\delta (G) \geq 2k$, then $G$ contains $k$ vertex-disjoint cycles, and furthermore, the minimum degree condition is best possible for all $n$ and $k$ where $n \geq 3k$. This serves as the motivation behind many results regarding best possible conditions that guarantee the existence of a fixed number of disjoint structures in graphs. For doubly chorded cycles, Qiao and Zhang proved that if $n \geq 4k$ and $\delta (G) \geq {\lfloor \frac{7k}{2} \rfloor}$, then $G$ contains $k$ vertex-disjoint doubly chorded cycles. However, the minimum degree in this result is sharp for only a finite number of values of $k$. Later, Gould Hirohata, and Horn improved upon this by showing that if $n \geq 6k$ and $\delta (G) \geq 3k$, then $G$ contains $k$ vertex-disjoint doubly chorded cycles. Furthermore, this minimum degree condition is best possible for all $n$ and $k$ where $n \geq 6k$. In this paper, we prove two results. First, we extend the result of Gould et al. by showing their minimum degree condition guarantees $k$ disjoint doubly chorded cycles even when $n \geq 5k$, and in addition, this is best possible for all $n$ and $k$ where $n \geq 5k$. Second, we improve upon the result of Qiao and Zhang by showing that every $n$-vertex graph $G$ with $n \geq 4k$ and $\delta (G) \geq {\lceil \frac{10k-1}{3} \rceil}$, contains $k$ vertex-disjoint doubly chorded cycles. Moreover, this minimum degree is best possible for all $k \in \mathbb{Z}^{+}$.

Keywords

cycles, chorded cycles, doubly chorded cycles, minimum degree

2010 Mathematics Subject Classification

Primary 05C35. Secondary 05C38.

The full text of this article is unavailable through your IP address: 18.117.74.47

The research of both authors was supported by the Grand Valley State University Student Summer Scholars Program.

Received 15 May 2020

Accepted 15 February 2023

Published 23 January 2024