Toughness of Graphs and $[a,b]$-Factors with Prescribed Properties

Abstract

Chvátal conjectured that if $G$ is a $k$-tough graph and $k|V(G)|$ is even, then $G$ has a $k$-factor. In $[5$ it was proved that Chvátal’s conjecture is true. Katerinis$[2]$ presented a toughness condition for a graph to have an $[a,b]$-factor. In this paper, we prove a stronger result: every $(a–1+a/b)$-tough graph satisfying all necessary conditions has an $[a,b]$-factor containing any given edge and another $[a,b]$-factor excluding it. We also discuss some special cases of the above result.