Hamiltonian cycles in subcubic graphs: what makes the problem difficult

We study the computational complexity of the Hamiltonian cycle problem in the class of graphs of vertex degree at most 3. Our goal is to distinguish boundary properties of graphs that make the problem difficult (NP-complete) in this domain. In the present paper, we discover the first boundary class of graphs for the Hamiltonian cycle problem in subcubic graphs