Number of Disjoint $5$-Cycles in Graphs

Abstract

Let $k\ge 1$, $l\ge 3$, and $s\ge 5$ be integers. In $1990$, Erdős and Faudree conjectured that if $G$ is a graph of order $4k$ with $\delta (G)\ge 2k$, then $G$ contains $k$ vertex-disjoint $4$-cycles. In this paper, we consider an analogous question for $5$-cycles; that is to say, if $G$ is a graph of order $5k$ with $\delta (G)\ge 3k$, then $G$ contains $k$ vertex-disjoint $5$-cycles? In support of this question, we prove that if $G$ is a graph of order $5k$ with ${\omega }_2(G)\ge 6l–2$, then, unless $\overline{K_{l-2}}+K_{2l+1,2l+1}\subseteq G\subseteq K_{l-2}+K_{2l+1,2l+1}$, $G$ contains $l–1$ vertex-disjoint $5$-cycles and a path of order $5$, which is vertex-disjoint from the $l–1$ $5$-cycles. In fact, we prove a more general result that if $G$ is a graph of order $5k+2s$ with ${\omega }_2(G)\ge 6k+2s$, then, unless $\overline{K_k}+K_{2k+s,2k+s}\subseteq G\subseteq K_k+K_{2k+s,2k+s}$, $G$ contains $k+1$ vertex-disjoint $5$-cycles and a path of order $2s–5$, which is vertex-disjoint from the $k+1$ $5$-cycles. As an application of this theorem, we give a short proof for determining the exact value of $\text{ex}(n,(k+1)C_5)$, and characterize the extremal graph.