Hamiltonian cycles in cubic graphs

In this work we study the complextity of Thomasson's algorithm over a special class of cubic graphs. This algorithm nds another hamiltonian circuit, if it starts with a rst one. An open problem is the complexity of this algorithm, but a class of cubic graphs has been found, where for each graph in this class, there exists a hamiltonian circuit and an edge on it, for which Thomasson's algorithm needs exponential number of steps. The goal of this work was to gure out, if Thomasson's algorithm needs exponential number of steps for any hamiltonian circuit and any edge on graphs from this class. We succeeded in proving, that indeed is so