3-连通无爪图的最长圈

Circumference in three-connected claw-free graphs

Hamilton问题是图论中重要的问题之一,已经得到了很多很好的结果,但一个图是Ham-ilton图的充分必要条件到现在还没有得出,于是开始研究无向图的最长圈,文章应用幅度的概念,使用反证法,通过构造最长圈并得出矛盾的方法,给出了3-连通无爪图最长圈的下限。

Hamilton problem is one of the most importance problems in Graph Theory, we have got many a- chievements, but there is no the result of what is the sufficient and necessary condition that a graph is a Hamihonian graph, so we begin to study the longest cycle in graph. In this paper, we introduce the definition of spoke number, by way of contradiction, we get the lower bound of circumference in 3 - connected claw - free graphs by the methods of constructing the longest cycle, it can be shown as .