Covering cycles andk-term degree sums

Abstract

We show that if$\sum\limits_{x \in S} {\deg _{G^x } \geqslant \left| G \right|}$, for every stable set$S \subseteq V\left( G \right),\left| S \right| = k$, then the vertex set ofG can be covered withk−1 cycles, edges or vertices. This settles a conjecture by Enomoto, Kaneko and Tuza.