Hamilton cycle of graph sigma2 >= n

Vũ Đình Hòa, Nguyễn Hữu Xuân Trường

Abstract


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.




DOI: https://doi.org/10.15625/1813-9663/28/2/2496

Journal of Computer Science and Cybernetics ISSN: 1813-9663

Published by Vietnam Academy of Science and Technology