Hamilton cycle of graph sigma2 >= n - Hòa, Vũ Đình; Trường, Nguyễn Hữu Xuân (Journal of Computer Science and Cybernetics, 2012)
Given a undirected and simple graph with n vertices, we denote by sigma_2 the minimum of degree sum of the pair of nonadjacent vertices in G and by sigma_2^*  the minimum of degree sum of the pair of nonadjacent vertices with distance 2.The problem HC to determine the Hamilton cycle (cycle passing all the vertices of the graph) is well-known a NPC problem. We consider the problem HC for the class of graphs satisfying sigma_2 >n  and for the class of graphs satisfying sigma_2^* >n, with given constant t. In this paper we give polynomial algorithm to estimate Hamilton cycle for the case t> 1 and prove that the problem HC remains a  NPC problem for the case t<1.