2025/10/27 by Bonvicini, S., Pisanski, T., Žitnik, A.
#05C25 #05C45 #05C70 #05C76 #05E18 #Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2510.23420
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 \pmod 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 ≤ 2. As a consequence we obtain that every connected bicirculant with s ≥ 3 is hamiltonian if m is a product of at most three prime powers. In particular, every connected bicirculant with s ≥ 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.