直径不超过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 axe 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)isHamiltonian.Moreover,by applying the closure concept of claw-free graphs introduced byby Ainouche et al.,which says that every 2-connected claw-free graph of diameter at most 2 is Hamiltonian.%不包含2K2的图是指不包含一对独立边作为导出子图的图.Kriesell证明了所有4连通的无爪图的线图是哈密顿连通的.本文证明了如果图G不包含2K2并且不同构与K2,P3和双星图,那么线图L(G)是哈密顿图,进一步应用由Ryj á(c)ek引入的闭包的概念,给出了直径不超过2的2连通无爪图是哈密顿图这个定理的新的证明方法.