|Table of Contents|

Hamiltonian Cycles in Regular 2-Connected Claw-Free Graphs(PDF)

Transactions of Tianjin University[ISSN:1006-4982/CN:12-1248/T]

Issue:
2003年04期
Page:
273-278
Publishing date:

Info

Title:
Hamiltonian Cycles in Regular 2-Connected Claw-Free Graphs
Author(s):
LI Ming-chu
(School of Electronic Information Engineering, Tianjin University, Tianjin 300072, China)
Keywords:
DOI:

Abstract:
A known result by Jackson Bill is that every 2-connected k-regular graph on at most 3k vertices is Hamiltonian. In this paper,it is proved that every 2-connected k-regular claw-free graph on at most 5k(k≥10)vertices is Hamiltonian. Moreover, the bound 5k is best possible. A counterexample of a 2-connected k-regular claw-free non-Hamiltonian graph on 5k+1 vertices is given, and it is conjectured that every 3-connected k-regular claw-free graph on at most 12k-7 vertices is Hamiltonian.

References

Memo

Memo:
-
Last Update: 2011-05-02