MathDB

The bicirculant Hamiltonicity conjecture

A bicirculant is a regular graph admitting a semiregular automorphism with two vertex-orbits of equal size; a graph is hamiltonian if it contains a Hamilton cycle. Let K2K_2 denote the complete graph on two vertices, and let G(m,2)G(m,2) be the generalized Petersen graph with parameters mm and 22.

Bicirculant Hamiltonicity conjecture. Every connected bicirculant, except for K2K_2 and the generalized Petersen graphs G(m,2)G(m,2) with m≡5(mod6)m\equiv 5\pmod 6, is hamiltonian.

The conjecture extends Brian Alspach’s classification of hamiltonian generalized Petersen graphs to all connected bicirculants. Hamiltonicity for bicirculants is widely open; in particular, the paper notes that it is not known whether all Cayley graphs on dihedral groups are hamiltonian.

Equivalent formulations 1

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

  1. The bicirculant hamiltonicity conjecture

    Let B(m;R,S,T)B(m;R,S,T) be a bicirculant, namely a regular graph admitting an automorphism with two vertex-orbits of equal size; in particular, K2K_2 denotes the complete graph on two vertices and G(m,2)G(m,2) denotes a generalized Petersen graph. A graph is hamiltonian if it has a Hamilton cycle.

    Bicirculant hamiltonicity conjecture. Every connected bicirculant, except for K2K_2 and the generalized Petersen graphs G(m,2)G(m,2) with m≡5(mod6)m\equiv 5\pmod 6, is hamiltonian.

    The conjecture extends Alspach's classification of non-hamiltonian generalized Petersen graphs and would contribute toward Lovász's conjecture that every connected vertex-transitive graph, apart from five known exceptions, has a Hamilton cycle. Its resolution remains open in the supplied source.

    source: Simona Bonvicini, Tomaž Pisanski and Arjana Žitnik, “On the hamiltonicity problem of bicirculants: a reduction to cyclic Haar graphs”, arXiv:2604.21607 (2026).

Sources & referencesView supporting material

Primary source

Simona Bonvicini, Tomaž Pisanski and Arjana Žitnik, “All generalized rose window graphs are hamiltonian”, arXiv:2504.16205 (2025).

bicirculantsgraph-theoryhamiltonian-cycleshamiltonian-graphs

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.