Number of Disjoint \(5\)-Cycles in Graphs

Abstract

Let \(k \geq 1\), \(l \geq 3\), and \(s \geq 5\) be integers. In \(1990\), Erdős and Faudree conjectured that if \(G\) is a graph of order \(4k\) with \(\delta(G) \geq 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) \geq 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) \geq 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) \geq 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.