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.

Full Text (PDF format)

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