(3,k)-Factor-Critical Graphs and Toughness |
| |
| Authors: | Minýong Shi Xudong Yuan Mao-cheng Cai Odile Favaron |
| |
| Institution: | (1) Institute of Systems Science, Academia Sinica, Beijing 100080, China, CN;(2) LRI, URA 410 CNRS, Ba^t. 410, Universite′ de Paris-Sud, 91405 Orsay cedex, France, FR |
| |
| Abstract: | 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. an r-regular spanning subgraph). Let t(G) denote the toughness of graph G. In this paper, we show that if t(G)≥4, then G is (3,k)-factor-critical for every non-negative integer k such that n+k even, k<2 t(G)−2 and k≤n−7.
Revised: September 21, 1998 |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
