POLYNOMIAL ALGORITHM TO DETERMINE HAMILTON CYCLE IN THE CLASS OF GRAPHS SATISFYING

Abstract

Given a undirected and simple graph with n vertices, we denote σ₂ the minimum of degree sum of the pair of nonadjacent vertices in G. In [1], the authors considered graphs with n vertices satisfying the conditon d(x)+d(y)=n-1 for all nonadjacent vertices X and Y and proved that the given graphs have Hamiltonian cycles (cycles containing all vertices of the graphs) iff n is odd and 2<α< ^n-1/2 where α is the independent number (the maximal number of the vertices pairwise non-adjacent). In this paper we consider a large class of graphs which satisfy the inecquality σ₂ ≥ n-1. We prove that all graphs with σ₂ ≥ n-1 have Hamilton cycles except some special graphs recognized by a polynomial algorithm