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

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

作　　者：安新慧[1] 刘晓平[2] 

机构地区：[1]新疆大学数学与系统科学学院,新疆乌鲁木齐830046 [2]新疆工业高等专科学校,新疆乌鲁木齐830091

出　　处：《运筹学学报》2008年第4期19-24,共6页Operations Research Transactions

基　　金：supported by NSFC (No.10601044),XJEDU2006S05;Scientific Research Foundation for Young Scholar of Xinjiang University.

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

关 键 词：运筹学 线图  无爪图  闭迹  哈密顿圈 

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