Is every connected bicirculant, apart from $K_2$ and the generalized Petersen graphs $G(m,2)$ with $m\equiv 5\pmod 6$, hamiltonian? (Bonvicini–Pisanski–Žitnik's bicirculant hamiltonicity conjecture)

A bicirculant is a regular graph admitting a semiregular automorphism with two vertex-orbits of equal size; the class contains generalized Petersen graphs, I-graphs, rose window graphs, generalized Tabačjn graphs, and cyclic Haar graphs (a family of Cayley graphs on dihedral groups). Alspach proved in 1983 that the only non-hamiltonian generalized Petersen graphs are $G(m,2)$ with $m\equiv 5\pmod 6$. Bonvicini, Pisanski and Žitnik (2025) conjectured that these, together with $K_2$, are the only non-hamiltonian connected bicirculants, and proved the conjecture for the quartic subcase $s=2$ (generalized rose window graphs). Subsequent work by the same authors (2025, 2026) verified the conjecture for all bicirculants with $|S|\le 3$ and for $|S|\ge 4$ with $m/\gcd(m,S)$ even, and reduced the entire valence-$\ge 4$ case to the hamiltonicity of connected cyclic Haar graphs of valence at least 4. The full conjecture — proof or counterexample — remains open as of August 2026.

Background

A Hamilton cycle in a graph is a cycle passing through every vertex exactly once; deciding which structured graph classes always contain one is a central theme of structural graph theory. A circulant is a Cayley graph on a cyclic group: vertices are elements of $\mathbb{Z}_m$ and edges join vertices differing by an element of a fixed connection set; every connected circulant is easily shown to be hamiltonian. The next structure up is a bicirculant: a regular, $d$-valent graph admitting a semiregular automorphism $\rho$ (an automorphism whose cycles all have the same length) with exactly two vertex-orbits $\{u_0,\dots,u_{m-1}\}$ and $\{v_0,\dots,v_{m-1}\}$ of size $m$. The vertices of each orbit induce a circulant of order $m$, and the remaining edges form a regular bipartite graph of valence $s$, $1\le s\le d$, between the two orbits. Concretely, for sets $R,T\subseteq\mathbb{Z}_m$ with $R=-R$, $T=-T$, $0\notin R\cup T$, and $S\subseteq\mathbb{Z}_m$ with $0\in S$, the bicirculant $B(m;R,S,T)$ has edges $u_iu_{i+j}$ for $j\in R$, $v_iv_{i+j}$ for $j\in T$, and spokes $u_iv_{i+j}$ for $j\in S$. The best-known bicirculants are the generalized Petersen graphs $G(m,k)$ (vertices $u_i,v_i$; edges $u_iu_{i+1}$, $u_iv_i$, $v_iv_{i+k}$; these are the bicirculants with $d=3$, $s=1$). Letting both rims jump instead of only the outer one gives the I-graphs $I(m;j,k)=B(m;\{j,-j\},\{0\},\{k,-k\})$, which contain the generalized Petersen graphs as the case $j=1$. Alspach's 1983 classification proved that among generalized Petersen graphs exactly the family $G(m,2)$ with $m\equiv 5\pmod 6$ — which includes the Petersen graph itself, $G(5,2)$ — fails to be hamiltonian. Related families: quartic (4-valent) bicirculants with $s=2$ are the generalized rose window graphs $R(m;a,b,c)=B(m;\{a,-a\},\{0,c\},\{b,-b\})$; adding a further spoke-type gives the pentavalent (5-valent) generalized Tabačjn graphs $T(m;a,b,c,d)=B(m;\{a,-a\},\{0,c,d\},\{b,-b\})$; bicirculants with $R=T=\emptyset$ (so $s=d$) are the cyclic Haar graphs $H(m;S)=B(m;\emptyset,S,\emptyset)$, which are exactly Cayley graphs on the dihedral group of order $2m$ whose connection set consists of reflections only. The broader context is the hamiltonicity of Cayley graphs: it is a well-known open problem whether every connected Cayley graph on a dihedral group has a Hamilton cycle (Alspach, Chen and Dean proved in 2010 that every such graph at least has a Hamilton path), and this is a special case of the classical conjecture of Lovász that every finite connected vertex-transitive graph (a graph whose automorphisms carry any vertex to any other), apart from a short list of known exceptions, has a Hamilton cycle. Since every Cayley graph on a dihedral group is a bicirculant, the question below strictly extends both the generalized Petersen classification and (part of) the dihedral Cayley problem. Bonvicini, Pisanski and Žitnik (2025) proved that all connected generalized rose window graphs are hamiltonian, verified that the conjecture below was already known for all cubic (3-valent) bicirculants, and posed the full conjecture for arbitrary valence; by 2026 the same authors verified it for all bicirculants with $|S|\le 3$ and reduced the remaining $|S|\ge 4$ case to cyclic Haar graphs of valence at least 4.

Problem Statement

Prove or refute Conjecture 1 of Bonvicini–Pisanski–Žitnik (arXiv:2504.16205): every connected bicirculant — in the standard model $B(m;R,S,T)$ with $R=-R$, $T=-T$, $0\notin R\cup T$, $0\in S$, over all $m\ge 1$ and all valences $d\ge 1$ — is hamiltonian, with the sole exceptions of $K_2=B(1;\emptyset,\{0\},\emptyset)$ (the complete graph on two vertices, the unique connected bicirculant of valence 1) and the generalized Petersen graphs $G(m,2)$ with $m\equiv 5\pmod 6$ — equivalently, a complete classification of non-hamiltonian connected bicirculants matching this exception list. By the 2026 reduction of the same authors, the case of valence $\ge 4$ is equivalent to the statement that every connected cyclic Haar graph $H(m;S)$ with $|S|\ge 4$ is hamiltonian.

References

1. Simona Bonvicini, Tomaž Pisanski, Arjana Žitnik, "All generalized rose window graphs are hamiltonian", arXiv:2504.16205 (2025), doi:10.48550/arXiv.2504.16205, https://arxiv.org/abs/2504.16205
2. Simona Bonvicini, Tomaž Pisanski, Arjana Žitnik, "On the Hamiltonian Bicirculants", arXiv:2510.23420 (2025), doi:10.48550/arXiv.2510.23420, https://arxiv.org/abs/2510.23420
3. Simona Bonvicini, Tomaž Pisanski, Arjana Žitnik, "On the hamiltonicity problem of bicirculants: a reduction to cyclic Haar graphs", arXiv:2604.21607 (2026), doi:10.48550/arXiv.2604.21607, https://arxiv.org/abs/2604.21607
4. Brian Alspach, "The classification of hamiltonian generalized Petersen graphs", Journal of Combinatorial Theory, Series B 34 (1983), 293–312, doi:10.1016/0095-8956(83)90042-4, https://doi.org/10.1016/0095-8956(83)90042-4
5. Brian Alspach, C. C. Chen, Matthew Dean, "Hamilton paths in Cayley graphs on generalized dihedral groups", Ars Mathematica Contemporanea 3 (2010), 29–47, doi:10.26493/1855-3974.101.a37, https://doi.org/10.26493/1855-3974.101.a37