On degree sum conditions for 2-factors with a prescribed number of cycles

Abstract

For a vertex subset $X$ of a graph $G$, let ${\Delta }_t(X)$ be the maximum value of the degree sums of the subsets of $X$ of size $t$. In this paper, we prove the following result: Let $k$ be a positive integer, and let $G$ be an $m$-connected graph of order $n\ge 5k-2$. If ${\Delta }_2(X)\ge n$ for every independent set $X$ of size $\lceil m/k\rceil +1$ in $G$, then $G$ has a 2-factor with exactly $k$ cycles. This is a common generalization of the results obtained by Brandt et al. [Degree conditions for 2-factors, J. Graph Theory 24 (1997) 165-173] and Yamashita [On degree sum conditions for long cycles and cycles through specified vertices, Discrete Math. 308 (2008) 6584-6587], respectively.

arXiv comment11 pages, 2 figures