IJPAM: Volume 32, No. 4 (2006)

A CONJECTURE OF CLAW-FREE HAMILTONIAN GRAPHS
WITH NEIGHBORHOOD UNION

Kewen Zhao
Department of Mathematics
University of Qiongzhou
Wuzhishan, Hainan, 572200, P.R. CHINA
e-mail: kewen@bxemail.com


Abstract.R.J. Faudree et al obtained that if $G$ is a 3-connected claw-free graph of order $n$, and $\vert N(u) \cup N(v)\vert \ge (2n-3)/3$ for each pair of nonadjacent vertices $u$, $v$, then $G$ is Hamiltonian. They conjectured that if $G$ is a 3-connected claw-free graph of order $n$, and $\vert N(u) \cup N(v)\vert \ge (2n-6)/3$ for each pair of nonadjacent vertices $u$, $v$, then $G$ is Hamiltonian. This paper we prove that if $G$ is a 3-connected claw-free graph of order $n$, and $\vert N(u) \cup N(v)\vert \ge (2n-7)/3$ for each pair of nonadjacent vertices $u$, $v$, then $G$ is Hamiltonian.

Received: November 28, 2004

AMS Subject Classification: 05C45, 05C38

Key Words and Phrases: claw-free graphs, neighborhood unions, Hamiltonian graphs

Source: International Journal of Pure and Applied Mathematics
ISSN: 1311-8080
Year: 2006
Volume: 32
Issue: 4