| 直径不超过2的2连通无爪图是哈密顿图 |
| |
| 引用本文： | 安新慧,刘晓平.直径不超过2的2连通无爪图是哈密顿图[J].运筹学学报,2008,12(4). |
| |
| 作者姓名： | 安新慧 刘晓平 |
| |
| 作者单位： | 1. 新疆大学数学与系统科学学院,新疆乌鲁木齐,830046
2. 新疆工业高等专科学校,新疆乌鲁木齐,830091 |
| |
| 基金项目： | 国家自然科学基金
，
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连通无爪图是哈密顿图这个定理的新的证明方法.
|
| 关 键 词： | 运筹学 线图 无爪图 闭迹 哈密顿圈 |
All 2-Connected Claw-Free Graphs with Diameter at Most TWO are Hamiltonian |
| |
| An Xinhui,Liu Xiaoping.All 2-Connected Claw-Free Graphs with Diameter at Most TWO are Hamiltonian[J].OR Transactions,2008,12(4). |
| |
| Authors: | An Xinhui Liu Xiaoping |
| |
| Abstract: | 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. |
| |
| Keywords: | Operations research line graphs claw-free graphs closed trail Hamilton cycle |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
