Hamiltonian Cycles in Regular 2-Connected Claw-Free Graphs  

作　　者：李明楚 

机构地区：[1]School of Electronic Information Engineering

出　　处：《Transactions of Tianjin University》2003年第4期273-278,共6页天津大学学报（英文版）

基　　金：SupportedbytheprojectT23ofLiuHuiCenterforAppliedMathematicsofNankaiUniversityandTianjinUniversity,andtheproject2 0 0 2AA1 4 2 0 1 0ofNational 863Plans

摘　　要：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.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.

关 键 词：Hamiltonian cycle REGULAR claw-free graph CIRCUMFERENCE 

分 类 号：O157.5[理学—数学]