The Complexity of HCP in Digraps with Degree Bound Two

Abstract

The Hamiltonian cycle problem (HCP) in digraphs D with degree bound two is solved by two mappings in this paper. The first bijection is between an incidence matrix C_{nm} of simple digraph and an incidence matrix F of balanced bipartite undirected graph G; The second mapping is from a perfect matching of G to a cycle of D. It proves that the complexity of HCP in D is polynomial, and finding a second non-isomorphism Hamiltonian cycle from a given Hamiltonian digraph with degree bound two is also polynomial. Lastly it deduces P=NP base on the results.

arXiv comment10 pages, 4 figures, had been submitted to a Journal

Cited by in corpus (2)

• The Complexity of Determining Existence a Hamiltonian Cycle is $O(n^3)$
• Some sufficient conditions on Hamiltonian digraph