On the hamiltonicity problem of bicirculants: a reduction to cyclic Haar graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915951928147968 |
|---|---|
| author | Bonvicini, Simona Pisanski, Tomaž Žitnik, Arjana |
| author_facet | Bonvicini, Simona Pisanski, Tomaž Žitnik, Arjana |
| contents | 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 \ge 1$ and sets $R, S, T \subseteq \mathbb Z_m$ such that $R=-R$, $T=-T$, $0 \not\in R \cup T$ and $0 \in S$, the graph $B(m;R,S,T)$ has vertex set $V=\{u_0,\dots,u_{m-1},v_0,\dots,v_m-1\}$ and edge set $E=\{u_iu_{i+j}| \ i \in\mathbb Z_m, j \in R\} \cup \{v_iv_{i+j}| \ i \in\mathbb Z_m, j \in T\} \cup\{u_iv_{i+j}| \ i \in\mathbb Z_m, j \in S\}.$ Bicirculant graphs with $R=T=\emptyset$ are known as cyclic Haar graphs.
In 2025 we conjectured that the only non-hamiltonian graphs among regular connected bicirculants of degree more than one are the generalized Petersen graphs $G(m,2)$ with $m \equiv 5 \pmod 6$. Recently we have verified the conjecture for bicirculants with $|S|\le 2$ and for bicirculants with $|R|=|T|$ odd.
In this paper we show that the conjecture holds for all bicirculants with $|S| \le 3$ and for all bicirculants with $|S| \ge 4$ and $m/\gcd(m, S)$ even. As a byproduct of our results, we prove that every connected bicirculant graph on $2m$ vertices with $|S| \ge 4$ is hamiltonian for even $m< 9\, 240$, and for odd $m< 3\,465$. Finally, we show that the existence of a hamilton cycle in every connected cyclic Haar graph of valence at least $4$ implies that every connected bicirculant graph of valence at least $4$ is hamiltonian. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_21607 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the hamiltonicity problem of bicirculants: a reduction to cyclic Haar graphs Bonvicini, Simona Pisanski, Tomaž Žitnik, Arjana Combinatorics 05C45, 05C25, 05C76, 05C70, 05E18 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 \ge 1$ and sets $R, S, T \subseteq \mathbb Z_m$ such that $R=-R$, $T=-T$, $0 \not\in R \cup T$ and $0 \in S$, the graph $B(m;R,S,T)$ has vertex set $V=\{u_0,\dots,u_{m-1},v_0,\dots,v_m-1\}$ and edge set $E=\{u_iu_{i+j}| \ i \in\mathbb Z_m, j \in R\} \cup \{v_iv_{i+j}| \ i \in\mathbb Z_m, j \in T\} \cup\{u_iv_{i+j}| \ i \in\mathbb Z_m, j \in S\}.$ Bicirculant graphs with $R=T=\emptyset$ are known as cyclic Haar graphs. In 2025 we conjectured that the only non-hamiltonian graphs among regular connected bicirculants of degree more than one are the generalized Petersen graphs $G(m,2)$ with $m \equiv 5 \pmod 6$. Recently we have verified the conjecture for bicirculants with $|S|\le 2$ and for bicirculants with $|R|=|T|$ odd. In this paper we show that the conjecture holds for all bicirculants with $|S| \le 3$ and for all bicirculants with $|S| \ge 4$ and $m/\gcd(m, S)$ even. As a byproduct of our results, we prove that every connected bicirculant graph on $2m$ vertices with $|S| \ge 4$ is hamiltonian for even $m< 9\, 240$, and for odd $m< 3\,465$. Finally, we show that the existence of a hamilton cycle in every connected cyclic Haar graph of valence at least $4$ implies that every connected bicirculant graph of valence at least $4$ is hamiltonian. |
| title | On the hamiltonicity problem of bicirculants: a reduction to cyclic Haar graphs |
| topic | Combinatorics 05C45, 05C25, 05C76, 05C70, 05E18 |
| url | https://arxiv.org/abs/2604.21607 |