Hamiltonian Cycles in Almost Claw-Free Graphs |
| |
Authors: | MingChu Li |
| |
Institution: | (1) Department of Mathematics, University of Toronto, 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 the following two results and conjecture that every 5-connected almost claw-free graph is hamiltonian. (1). Every 2-connected
almost claw-free graph G∉J on n≤ 4 δ vertices is hamiltonian, where J is the set of all graphs defined as follows: any graph G in J can be decomposed into three disjoint connected subgraphs G
1, G
2 and G
3 such that E
G
(G
i
, G
j
) = {u
i
, u
j
, v
i
v
j
} for i≠j and i,j = 1, 2, 3 (where u
i
≠v
i
∈V(G
i
) for i = 1, 2, 3). Moreover the bound 4δ is best possible, thereby fully generalizing several previous results. (2). Every 3-connected
almost claw-free graph on at most 5δ−5 vertices is hamiltonian, hereby fully generalizing the corresponding result on claw-free
graphs.
Received: September 21, 1998 Final version received: August 18, 1999 |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|