A Note on the Hamiltonian Circuit Problem on Directed Path Graphs

Abstract

Bertossi and Bonuccelli [2] proved that the Hamiltonian Circuit problem in NP-Complete even when the inputs are restricted to the special class of Undirected Path graphs. The corresponding problem on Directed Path graphs was left as an open problem. We use a characterization of Directed Path graphs due to Monma and Wei [8] to prove that the Hamiltonian Circuit problem and the Hamiltonian Path problem are NP-Complete on Directed Path graphs.