A comprehensive analysis of degree based condition for Hamiltonian cycles

作者：Hasan Md Kamrul; Kaykobad Mohammad; Lee Young Koo; Lee Sungyoung^*

来源：Theoretical Computer Science, 2010, 411(1): 285-287.

DOI：10.1016/j.tcs.2009.09.018

• Hamiltonian cycle
• Hamiltonian path
• Graphs

Since finding whether a graph has a Hamiltonian path or Hamiltonian cycle are both NP-complete problems, researchers have been formulating sufficient conditions that ensure the path or cycle. Rahman and Kaykobad (2005) [2] presented a sufficient condition for determining the existence of Hamiltonian path. Three recent works - Lenin Mehedy, Md. Kamrul Hasan, Mohammad Kaykobad (2007) [3], Rao Li (2006) [4], Shengjia Li, Ruijuan Li, Jinfeng Feng (2007) [5] - further used the same or similar condition to ensure Hamiltonian cycle with some exceptions. The three works, along with their unique findings, have some common results. This paper unifies the results and brings them under Rahman and Kaykobad's condition.

• 出版日期2010-1-1