Longest Cycles in Almost Claw-Free Graphs

Some known results on claw-free graphs are generalized to the larger class of almost claw-free graphs. In this paper, we prove several properties on longest cycles in almost claw-free graphs. In particular, we show the following two results.? (1) Every 2-connected almost claw-free graph on n vertices contains a cycle of length at least min {n, 2δ+4} and the bound 2δ+ 4 is best possible, thereby fully generalizing a result of Matthews and Sumner.? (2) Every 3-connected almost claw-free graph on n vertices contains a cycle of length at least min {n, 4δ}, thereby fully generalizing a result of MingChu Li. Received: September 17, 1996 Revised: September 22, 1998