Mattias Timonen: The class of distance-hereditary graphs, the Hamiltonian problems and a linear time algorithm

This paper deals with graphs and graph algortihms for solving the Hamiltonian Problems. We consider the class of distance-herditary graphs, for which there exist linear time algorithms for determining whether a given distance-hereditary graph is Hamiltonian or not. We present such an algorithm. We also give a new idea on the existence of Hamiltonian cycle in graphs that are not trivially non-hamiltonian. We give an algorithm, based on this new idea, for solving the Hamiltonian Problem on graphs with maximum degree gerater than one. Each algorithm is exemplified.