Hamilton cycle of graph sigma2 >= n

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

Authors

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

DOI:

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

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.

Metrics

Metrics Loading ...

How to Cite

[1]
V. Đình Hòa and N. H. X. Trường, “Hamilton cycle of graph sigma2 >= n”, JCC, vol. 28, no. 2, pp. 153–160, Oct. 2012.

Issue

Section

Computer Science