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.
- \(R(C_n,C_n,C_n)\leqq (4+o(1))n\)
- An Improved Bound for Vertex Partitions by Connected Monochromatic K-Regular Graphs
- Analyzing randomized search heuristics: tools from probability theory
- Blow-up lemma
- Covering cycles and \(k\)-term degree sums
- Covering vertices by cycles
- Cycle lengths in graphs with large minimum degree
- Degree Sums and Covering Cycles
- Hamiltonian square-paths
- How to avoid using the regularity Lemma: Pósa's conjecture revisited
- scientific article; zbMATH DE number 4191728 (Why is no real title available?)
- scientific article; zbMATH DE number 3652373 (Why is no real title available?)
- scientific article; zbMATH DE number 3641497 (Why is no real title available?)
- scientific article; zbMATH DE number 878896 (Why is no real title available?)
- scientific article; zbMATH DE number 3262986 (Why is no real title available?)
- scientific article; zbMATH DE number 3344609 (Why is no real title available?)
- scientific article; zbMATH DE number 3400923 (Why is no real title available?)
- Local colourings and monochromatic partitions in complete bipartite graphs
- On the square of a Hamiltonian cycle in dense graphs
- Partitioning 2-edge-colored graphs by monochromatic paths and cycles
- Proof of a Packing Conjecture of Bollobás
- Proof of the Seymour conjecture for large graphs
- Pósa's conjecture for graphs of order at least 2 × 108
- Some Theorems on Abstract Graphs
- The 3-colored Ramsey number of even cycles
- The Blow-up Lemma
- The longest cycle of a graph with a large minimal degree
- The longest cycles in a graph G with minimum degree at least \(| G| /k\)
- The Ramsey number for a triple of long even cycles
- Covering cycles and \(k\)-term degree sums
- Embedding Graphs into Larger Graphs: Results, Methods, and Problems
- Cycle Partitions in Graphs
- Triangles in randomly perturbed graphs
- Covering cycles in sparse graphs
- The square of a Hamilton cycle in randomly perturbed graphs
- Cycle partitions in dense regular digraphs and oriented graphs
- Cycle partition of dense regular digraphs and oriented graphs (extended abstract)
This page was built for publication: Stability for vertex cycle covers
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2401441)
