Hamilton cycles in bicirculants with non-coprime connection sets
Abstract
A bicirculant is a regular graph that admits an automorphism having two vertex-orbits of the same size. A bicirculant can be described as follows. Given an integer m ≥ 1 and sets R, S, T ⊆ ℤm such that R=−R, T=−T, 0 not∈ R ∪ T and 0 ∈ S, the graph $B(m;R,S,T)$ has vertex set V={u0,…,um−1,v0,…,vm−1} and edge set E={uiui+j| i ∈ ℤm, j ∈ R} ∪ {vivi+j| i ∈ ℤm, j ∈ T} ∪ {uivi+j| i ∈ ℤm, j ∈ S}. Some of the well known bicirculants include the generalized Petersen graphs and Cayley graphs of dihedral groups. In 1983, Brian Alspach proved that the only non-hamiltonian generalized Petersen graphs are G(m,2) where m ≡ 5 pmod 6. In a recent paper we conjectured that this is the only exception among regular connected bicirculants of degree at least two, and we have verified the conjecture for bicirculants with |S|≤ 3. Results of Alspach, Chen and Dean imply that the conjecture also holds for all bicirculants with m even and gcd(m,S)=1. In this paper, we show that the conjecture holds for all bicirculants with |S| ≥ 4 and gcd(m,S)>1 such that R∪ T contains an element that is not coprime to gcd(m,S) and, if m is odd, is also not divisibile by gcd(m, S) or R ∩ T contains an element that is coprime to gcd(m,S).
Related
- On Hamilton cycles in quasiprimitive graphs of order 2pq
- Alternating Hamilton Paths and Cycles in Poset Products
- On the Minimum Number of Hamilton Cycles in Hamiltonian Threshold Graphs: A Simple Proof
- Tournaments with many Hamilton cycles
- Hitting time for loose Hamilton cycles in the random hypergraph process
BibTeX
@misc{bonvicini2026hamilton,
title = {{Hamilton cycles in bicirculants with non-coprime connection sets}},
author = {Simona Bonvicini and Tomaž Pisanski and Arjana Žitnik},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.05531},
eprint = {2611.05531},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.05531},
note = {CC BY-NC-ND 4.0},
}
RIS
TY - UNPB
TI - Hamilton cycles in bicirculants with non-coprime connection sets
AU - Simona Bonvicini
AU - Tomaž Pisanski
AU - Arjana Žitnik
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2611.05531
UR - https://arxiv.org/abs/2611.05531
AB - A bicirculant is a regular graph that admits an automorphism having two vertex-orbits of the same size. A bicirculant can be described as follows. Given an integer m ≥ 1 and sets R, S, T ⊆ ℤ_m such that R=−R, T=−T, 0 not∈ R ∪ T and 0 ∈ S, the graph $B(m;R,S,T)$ has vertex set V={u_0,…,u_m−1,v_0,…,v_m−1} and edge set E={u_iu_i+j| i ∈ ℤ_m, j ∈ R} ∪ {v_iv_i+j| i ∈ ℤ_m, j ∈ T} ∪ {u_iv_i+j| i ∈ ℤ_m, j ∈ S}. Some of the well known bicirculants include the generalized Petersen graphs and Cayley graphs of dihedral groups. In 1983, Brian Alspach proved that the only non-hamiltonian generalized Petersen graphs are G(m,2) where m ≡ 5 pmod 6. In a recent paper we conjectured that this is the only exception among regular connected bicirculants of degree at least two, and we have verified the conjecture for bicirculants with |S|≤ 3. Results of Alspach, Chen and Dean imply that the conjecture also holds for all bicirculants with m even and gcd(m,S)=1. In this paper, we show that the conjecture holds for all bicirculants with |S| ≥ 4 and gcd(m,S)>1 such that R∪ T contains an element that is not coprime to gcd(m,S) and, if m is odd, is also not divisibile by gcd(m, S) or R ∩ T contains an element that is coprime to gcd(m,S).
ER -