TY - JOUR

T1 - Stability for vertex cycle covers

AU - Balogh, József

AU - Mousset, Frank

AU - Skokan, Jozef

N1 - Funding Information:
∗Research is partially supported by Simons Fellowship, NSF CAREER Grant DMS-0745185, Marie Curie FP7-PEOPLE-2012-IIF 327763. †Supported by grant no. 6910960 of the Fonds National de la Recherche, Luxembourg.
Publisher Copyright:
© 2017, Australian National University. All rights reserved.

PY - 2017/9/8

Y1 - 2017/9/8

N2 - In 1996 Kouider and Lonc proved the following natural generalization of Dirac’s Theorem: for any integer k ≥ 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 In,k = Kn\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 k1,…,kr summing to k, the disjoint union Ik1n/k,k1 + · ·· + Ikr n/k,kr 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 Ik1n/k,k1 + · ·· + Ikr n/k,kr, for some sequence k1,…,kr of positive integers that sum to k. Our proof uses Szemerédi’s Regularity Lemma and the related machinery.

AB - In 1996 Kouider and Lonc proved the following natural generalization of Dirac’s Theorem: for any integer k ≥ 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 In,k = Kn\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 k1,…,kr summing to k, the disjoint union Ik1n/k,k1 + · ·· + Ikr n/k,kr 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 Ik1n/k,k1 + · ·· + Ikr n/k,kr, for some sequence k1,…,kr of positive integers that sum to k. Our proof uses Szemerédi’s Regularity Lemma and the related machinery.

UR - http://www.scopus.com/inward/record.url?scp=85029153770&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85029153770&partnerID=8YFLogxK

U2 - 10.37236/5185

DO - 10.37236/5185

M3 - Article

AN - SCOPUS:85029153770

SN - 1077-8926

VL - 24

JO - Electronic Journal of Combinatorics

JF - Electronic Journal of Combinatorics

IS - 3

M1 - #P3.56

ER -