On the Complexity of Determining Whether there is a Unique Hamiltonian Cycle or Path

Olivier Hudry, Antoine Lobstein

The decision problems of the existence of a Hamiltonian cycle or of a Hamiltonian path in a given graph, and of the existence of a truth assignment satisfying a given Boolean formu…