Toughness of Graphs and $k$-Factors with Given Properties

Abstract

Chvatal [1] presented the conjecture that every $k$-tough graph $G$ has a $k$-factor if $G$ satisfies trivial necessary conditions. The truth of Chvatal’s conjecture was proved by Enomoto $etal$ [2]. Here we prove the following stronger results: every
$k$-tough graph satisfying trivial necesary conditions has a k-factor which contains an arbitrarily given edge if $k\ge 2$, and also has a $k$-factor which does not contain an arbitrarily given edge $v(k\ge 1)$.