On the Hamiltonian Bicirculants

A bicirculant is a regular graph that admits a semi-regular automorphism with two vertex-orbits of the same size. By m we denote the size of vertex-orbits and by d the valence of a bicirculant. Furthermore, we denote by s the valence of the bipartite graph joining the two vertex-orbits. In 1983, Brian Alspach proved that the only non-hamiltonian generalized Petersen graphs are G(m,2) with m \equiv 5 mod 6. In a recent paper we conjectured that this is the only exception among regular, connected bicirculants of degree d > 1 and we have verified the conjecture for the quartic bicirculants with s=2, also known as the generalized rose window graphs. In this paper we develop tools and apply them for a partial verification of the conjecture. We show that the conjecture holds for all bicirculants with s \leq 2. As a consequence we obtain that every connected bicirculant with s \ge 3 is hamiltonian if m is a product of at most three prime powers. In particular, every connected bicirculant with s \ge 3 is hamiltonian for even m<210 and odd m < 1155. Our results imply that many other families of bicirculants are hamiltonian. For example, all bicirculants with d-s odd are hamiltonian.