(2,k)-Factor-Critical Graphs and Toughness

 A graph is (r,k)-factor-critical if the removal of any set of k vertices results in a graph with an r-factor (i.e. with an r-regular spanning subgraph). We show that every τ-tough graph of order n with τ≥2 is (2,k)-factor-critical for every non-negative integer k≤min{2τ−2, n−3}, thus proving a conjecture as well as generalizing the main result of Liu and Yu in 4]. Received: December 16, 1996 / Revised: September 17, 1997