Stability for vertex cycle covers (Q2401441): Difference between revisions

Summary: \textit{M. Kouider} and \textit{Z. Lonc} [Combinatorica 16, No. 3, 407--412 (1996; Zbl 0857.05058)] proved the following natural generalization of Dirac's theorem: for any integer \(k\geq 2\), if \(G\) is an \(n\)-vertex graph with minimum degree at least \(n/k\), then there are \(k-1\) cycles in \(G\) that together cover all the vertices.{ }This is tight in the sense that there are \(n\)-vertex graphs that have minimum degree \(n/k-1\) and that do not contain \(k-1\) cycles with this property. A concrete example is given by \(I_{n,k} = K_n\backslash K_{(k-1)n/k+1}\) (an edge-maximal graph on \(n\) vertices with an independent set of size \((k-1)n/k+1\)). This graph has minimum degree \(n/k-1\) and cannot be covered with fewer than \(k\) cycles. More generally, given positive integers \(k_1,\ldots,k_r\) summing to \(k\), the disjoint union \(I_{k_1n/k,k_1}+ \cdots + I_{k_rn/k,k_r}\) is an \(n\)-vertex graph with the same properties.{ }In this paper, we show that there are no extremal examples that differ substantially from the ones given by this construction. More precisely, we obtain the following stability result: if a graph \(G\) has \(n\) vertices and minimum degree nearly \(n/k\), then it either contains \(k-1\) cycles covering all vertices, or else it must be close (in 'edit distance') to a subgraph of \(I_{k_1n/k,k_1}+ \cdots + I_{k_rn/k,k_r}\), for some sequence \(k_1,\ldots,k_r\) of positive integers that sum to \(k\).{ }Our proof uses Szemerédi's regularity lemma and the related machinery.