Longest Cycles in Almost Claw-Free Graphs |
| |
Authors: | MingChu Li |
| |
Institution: | (1) Department of Mathematics, University of Toronto, 100 St. George Street, Toronto, Ontario M5S 3G3, Canada, CA |
| |
Abstract: | 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 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|