直径不超过2的2连通无爪图是哈密顿图(英文)

All 2-Connected Claw-Free Graphs with Diameter at Most Two are Hamiltonian

不包含2K_2的图是指不包含一对独立边作为导出子图的图.Kriesell证明了所有4连通的无爪图的线图是哈密顿连通的.本文证明了如果图G不包含2K_2并且不同构与K_2,P_3和双星图,那么线图L(G)是哈密顿图,进一步应用由Ryjá(?)ek引入的闭包的概念,给出了直径不超过2的2连通无爪图是哈密顿图这个定理的新的证明方法.

A graph is called 2K2-free if it does not contain an independent pair of edges as an induced subgraph. Kriesell proved that all 4-connected line graphs of claw-free graph are Hamiltonian-connected. Motivated from this, in this note, we show that if G is 2K2-free and is not isomorphic to K2, P3 or a double star, then the line graph L（G） is Hamiltonian. Moreover, by applying the closure concept of claw-free graphs introduced by Ryjacek , we provide another proof for a theorem, obtained by Gould and independently by Ainouche et al., which says that every 2-connected claw-free graph of diameter at most 2 is Hamiltonian.