Title: Simple Necessary Conditions for the Existence of a Hamiltonian Path with Applications to Cactus Graphs,
Abstract: We describe some necessary conditions for the existence of a Hamiltonian path
in any graph (in other words, for a graph to be traceable). These conditions
result in a linear time algorithm to decide the Hamiltonian path problem for
cactus graphs. We apply this algorithm to several molecular databases to report
the numbers of graphs that are traceable cactus graphs.