TOUGHNESS AND HAMILTONICITY IN ALMOST CLAW-FREE GRAPHS

Some known results on claw-free (K-1,K-3-free) graphs are generalized to the larger class of almost claw-free graphs which were introduced b y Ryjacek. In particular, we show that a 2-connected almost claw-free graphis 1-tough, and that a 2-connected almost claw-free graph on n ve rtices is hamiltonian if delta greater than or equal to 1/3(n - 2), th ereby (partly) generalizing results of Matthews and Sumner. Finally, w e use a result of Bauer et al. to show that a 2-connected almost claw- free graph on n vertices is hamiltonian if d(u) + d(v) + d(w) greater than or equal to n for all independent sets of vertices u, v, and w. ( C) 1996 John Wiley & Sons, Inc.