A comprehensive analysis of degree based condition for Hamiltonian cycles

摘要

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.