Improved degree conditions for Hamiltonian properties

详细信息	查看全文 | 推荐本文 |

• 作者：Arnfried Kemnitz^a ; ^{a.kemnitz@tu-bs.de} ; Ingo Schiermeyer^b ; ^{Ingo.Schiermeyer@tu-freiberg.de}
• 关键词：Hamiltonian ; Hamiltonian-connected ; Traceable ; Bondy&rsquo ; s Theorem ; Degree sum conditions
• 刊名：Discrete Mathematics
• 出版年：2012
• 期刊代码：47_0012365x
• 类别：cp
• 出版时间：28 July, 2012
• 卷：312
• 期：14
• 页码：2140-2145
• 文件大小：210 K

摘要

In 1980, Bondy proved that for an integer a -connected graph of order is traceable () or Hamiltonian () or Hamiltonian-connected () if the degree sum of every set of pairwise nonadjacent vertices is at least . This generalizes the well-known sufficient conditions of Dirac () and Ore (). The condition in Bondy鈥檚 Theorem is not tight for . We improve this sufficient degree condition and show the general tightness of this result.