  We show how to find a Hamiltonian cycle in a graph of degree at most three
with n vertices, in time O(2^{n/3}) ~= 1.260^n and linear space. Our algorithm
can find the minimum weight Hamiltonian cycle (traveling salesman problem), in
the same time bound. We can also count or list all Hamiltonian cycles in a
degree three graph in time O(2^{3n/8}) ~= 1.297^n. We also solve the traveling
salesman problem in graphs of degree at most four, by randomized and
deterministic algorithms with runtime O((27/4)^{n/3}) ~= 1.890^n and
O((27/4+epsilon)^{n/3}) respectively. Our algorithms allow the input to specify
a set of forced edges which must be part of any generated cycle. Our cycle
listing algorithm shows that every degree three graph has O(2^{3n/8})
Hamiltonian cycles; we also exhibit a family of graphs with 2^{n/3} Hamiltonian
cycles per graph.
