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 ≡ 5 6 m ≡ 5 ( mod 6 ) . In a recent paper, we conjectured that this is the only exception among regular, connected bicirculants of degree $$d > 1$$ d > 1 and we have verified the conjecture for the quartic bicirculants with $$s=2$$ 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 ≤ 2 s ≤ 2 . As a consequence, we obtain that every connected bicirculant with s ≥ 3 s ≥ 3 is Hamiltonian if m is a product of at most three prime powers. In particular, every connected bicirculant with s ≥ 3 s ≥ 3 is Hamiltonian for even $$m<210$$ m < 210 and odd $$m < 1155$$ m < 1155 . Our results imply that many other families of bicirculants are Hamiltonian. For example, all bicirculants with $$d-s$$ d - s odd are Hamiltonian.