  The Hamiltonian cycle problem is to decide whether a given graph has a
Hamiltonian cycle. Bertossi and Bonuccelli (1986, Information Processing
Letters, 23, 195-200) proved that the Hamiltonian Cycle Problem is NP-Complete
even for undirected path graphs and left the Hamiltonian cycle problem open for
directed path graphs. Narasimhan (1989, Information Processing Letters, 32,
167-170) proved that the Hamiltonian Cycle Problem is NP-Complete even for
directed path graphs and left the Hamiltonian cycle problem open for rooted
directed path graphs. In this paper we resolve this open problem by proving
that the Hamiltonian Cycle Problem is also NP-Complete for rooted directed path
graphs.
