POLYNOMIAL ALGORITHM DEFINES HAMILTONIAN CYCLE OF THE GRAPH FROM ITS CLOSURE

Abstract

Given an undirected graph G=(V,E), where V = {v1, v2, ..., vp} is the vertex set and E is the edge set of G. A cycle C in G is called a Hamiltonian cycle if C containes all vertices of G. The closure of G is the graph obtained from G by recursively joining pairs of nonadjacent vertices whose degree sum is at least p until no such pair remains. We use cl(G) to denote the closure of G [9]. In this paper we shall present a polynomial algorithm to define a Hamiltonian cycle of G from a given Hamiltonian cycle C in cl(G).