pith. sign in

arxiv: 2604.21607 · v1 · submitted 2026-04-23 · 🧮 math.CO

On the hamiltonicity problem of bicirculants: a reduction to cyclic Haar graphs

Simona Bonvicini , Toma\v{z} Pisanski , Arjana \v{Z}itnik This is my paper

Pith reviewed 2026-05-09 21:22 UTC · model grok-4.3

classification 🧮 math.CO MSC 05C4505C25
keywords bicirculant graphsHamiltonicitycyclic Haar graphsgeneralized Petersen graphsHamilton cyclesregular graphsgraph automorphisms
0
0 comments X

The pith

The Hamiltonicity of connected bicirculants reduces to that of cyclic Haar graphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper examines when regular bicirculant graphs of degree greater than 1 contain Hamilton cycles. It proves the authors' earlier conjecture in two new families: all connected bicirculants with connection set size |S| at most 3, and all with |S| at least 4 when m divided by gcd(m, S) is even. The central contribution is a reduction theorem showing that if every connected cyclic Haar graph of valence at least 4 is Hamiltonian, then every connected bicirculant of valence at least 4 is Hamiltonian. The result narrows an open question to the simpler subclass of cyclic Haar graphs, where the two connection sets R and T are empty, while also giving explicit Hamiltonicity for all |S| >= 4 bicirculants below certain size thresholds on m.

Core claim

The authors establish that the only non-Hamiltonian connected regular bicirculants of degree more than one are the generalized Petersen graphs G(m,2) with m congruent to 5 modulo 6, at least when |S| <= 3 and when |S| >= 4 with m/gcd(m,S) even. They derive explicit bounds showing every connected bicirculant on 2m vertices with |S| >= 4 is Hamiltonian for even m less than 9240 and odd m less than 3465. They prove that Hamiltonicity of all connected cyclic Haar graphs of valence at least 4 implies Hamiltonicity of all connected bicirculants of valence at least 4.

What carries the argument

The reduction from a general bicirculant B(m; R, S, T) to the cyclic Haar graph B(m; empty, S, empty), using the two-orbit automorphism and the symmetry conditions R = -R, T = -T, 0 not in R union T, and 0 in S.

Load-bearing premise

The bicirculants are connected and regular of degree greater than 1, the connection sets satisfy the stated symmetry conditions, and the reduction from general bicirculants to cyclic Haar graphs preserves Hamilton cycles.

What would settle it

A single connected cyclic Haar graph of valence at least 4 with no Hamilton cycle would show that the reduction does not force all bicirculants to be Hamiltonian.

Figures

Figures reproduced from arXiv: 2604.21607 by Arjana \v{Z}itnik, Simona Bonvicini, Toma\v{z} Pisanski.

Figure 1
Figure 1. Figure 1: The construction of a hamilton cycle we give in the proof of Lemma [10, [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Step 1 in the proof of Lemma 4.3. The figure shows a bicirculant graph [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Step 2 in the proof of Lemma 4.3. We extend the hamilton cycle [PITH_FULL_IMAGE:figures/full_fig_p014_3.png] view at source ↗
read the original 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 \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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript addresses the Hamiltonicity of bicirculant graphs by proving the 2025 conjecture for bicirculants with |S| ≤ 3 and for |S| ≥ 4 when m/gcd(m, S) is even. It further establishes that the Hamiltonicity of all connected cyclic Haar graphs of valence at least 4 would imply Hamiltonicity for all connected bicirculants of valence at least 4. As a byproduct, it provides explicit upper bounds on m for which all connected bicirculants with |S| ≥ 4 are Hamiltonian.

Significance. This work provides meaningful progress toward resolving the bicirculant Hamiltonicity conjecture through targeted case analysis and a key reduction to cyclic Haar graphs. The derived bounds on m enable computational checks for small instances, and the reduction highlights the central role of cyclic Haar graphs in the problem. These contributions are valuable for the field of graph theory, particularly in understanding Hamiltonian properties of vertex-transitive or nearly transitive graphs.

minor comments (3)
  1. [Abstract] The notation for the vertex set contains a typographical error: 'v_0,…,v_m-1' should be 'v_0,…,v_{m-1}'.
  2. [Abstract] The term 'valence' is used interchangeably with 'degree'; consistency in terminology would improve clarity.
  3. The paper mentions previous verification for |S|≤2 and |R|=|T| odd, but does not cite the specific reference for the 2025 conjecture or the recent verifications.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, recognition of the significance of our results on the bicirculant Hamiltonicity conjecture, and recommendation for minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The manuscript advances partial proofs of the authors' own 2025 conjecture via explicit case analysis on the size of S and a reduction theorem linking general bicirculants to the special case of cyclic Haar graphs (R = T = ∅). These steps rest on direct constructions that preserve the given symmetry conditions (R = −R, T = −T, 0 ∉ R ∪ T, 0 ∈ S) and connectedness; no equation, parameter fit, or ansatz is redefined in terms of its own output. The self-reference to the conjecture merely identifies the open problem being addressed and supplies no load-bearing premise for the new theorems. The derivation chain is therefore self-contained against external graph-theoretic benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the standard definitions of bicirculants, cyclic Haar graphs, Hamilton cycles, and graph automorphisms from prior literature; no free parameters, ad-hoc axioms, or new entities are introduced.

axioms (1)
  • standard math Standard axioms of undirected simple graphs, group actions on vertices, and the definition of Hamiltonian cycles.
    Invoked throughout the abstract when defining B(m;R,S,T) and stating Hamiltonicity.

pith-pipeline@v0.9.0 · 5736 in / 1516 out tokens · 42607 ms · 2026-05-09T21:22:32.691096+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

  1. [1]

    Alspach, The classification of Hamiltonian generalized Petersen graphs,J

    B. Alspach, The classification of Hamiltonian generalized Petersen graphs,J. Combin. Theory Ser. B34(1983), 293–312. 24

    work page 1983

  2. [2]

    Alspach, C.C

    B. Alspach, C.C. Chen, M. Dean, Hamilton paths in Cayley graphs on general- ized dihedral groups,Ars Math. Contemp.3(2010), 29–47

    work page 2010

  3. [3]

    Alspach, J

    B. Alspach, J. Liu, On the Hamilton connectivity of generalized Petersen graphs, Discrete Math.309(2009), 5461–5473

    work page 2009

  4. [4]

    Alspach, C

    B. Alspach, C. Q. Zhang, Hamilton cycles in cubic Cayley graphs on dihedral groups,Ars Combin.28(1989), 101–108

    work page 1989

  5. [5]

    Arroyo, I

    A. Arroyo, I. Hubard,K. Kutnar, E. O’Reilly, P. ˇSparl, Classification of symmet- ric Tabaˇ cjn graphs,Graphs Combin.31(2015), 1137–1153

    work page 2015

  6. [6]

    L. W. Berman, G. G´ evay, T. Pisanski, The Gray graph is a unit-distance graph, Art Discrete Appl. Math.8(2025), Article p1.03

    work page 2025

  7. [7]

    Boben, T

    M. Boben, T. Pisanski, Polycyclic configurations,European J. Combin.24 (2003), 431–457

    work page 2003

  8. [8]

    Bonvicini, T

    S. Bonvicini, T. Pisanski, A novel characterization of cubic Hamiltonian graphs via the associated quartic graphs.Ars Math. Contemp.12(2017), 1–24

    work page 2017

  9. [9]

    Bonvicini, T

    S. Bonvicini, T. Pisanski, A. ˇZitnik, All generalized rose window graphs are hamiltonian,Graphs Combin.42(2026), Article 27

    work page 2026

  10. [10]

    Bonvicini, T

    S. Bonvicini, T. Pisanski, A. ˇZitnik, On the Hamiltonian Bicirculants, arXiv:2510.23420 [math.CO], 2025

    work page arXiv 2025

  11. [11]

    Conder, I

    M. Conder, I. Est´ elyi, T. Pisanski, Vertex-transitive Haar graphs that are not Cayley graphs. In: Conder, M., Deza, A., Weiss, A. (eds)Discrete geometry and symmetry, volume 234 ofSpringer Proc. Math. Stat.pages 61–70. Springer, Cham, 2018

    work page 2018

  12. [12]

    I. Z. Bouwer, W. W. Chernoff, B. Monson, Z. Star, The Foster Census, Charles Babbage Research Centre, 1988

    work page 1988

  13. [13]

    J. L. Gross, T. W. Tucker,Topological Graph Theory, Dover books on mathe- matics, Dover Publications, 2001

    work page 2001

  14. [14]

    Gr¨ unbaum, Configurations of points and lines

    B. Gr¨ unbaum, Configurations of points and lines. InGraduate Studies in Math- ematicsvolume 103. American Mathematical Society, Providence, RI, 2009

    work page 2009

  15. [15]

    Hladnik, D

    M. Hladnik, D. Maruˇ siˇ c,T. Pisanski, Cyclic Haar graphs,Discrete Math.244 (2002),137–152

    work page 2002

  16. [16]

    Holszty´ nski, R

    W. Holszty´ nski, R. F. E. Strube, Paths and circuits in finite groups,Discrete Math.22(1978), 263–272

    work page 1978

  17. [17]

    Jasenˇ cakov´ a, R

    K. Jasenˇ cakov´ a, R. Jajcay, T. Pisanski, A new generalization of generalized Petersen graphs,Art Discrete Appl. Math.3(2020), Paper No. 1.04, 20

    work page 2020

  18. [18]

    Kutnar, D

    K. Kutnar, D. Maruˇ siˇ c,ˇS. Miklaviˇ c, R. Straˇ sek, Automorphisms of Tabaˇ cjn graphs,Filomat27(2013), 1157–1164. 25

    work page 2013

  19. [19]

    Malniˇ c, D

    A. Malniˇ c, D. Maruˇ siˇ c, P.ˇSparl, On strongly regular bicirculants,Eur. J. Comb. 28(2007), 891–900

    work page 2007

  20. [20]

    Maruˇ siˇ c, On vertex symmetric digraphs,Discrete Math.36(1981), 69–81

    D. Maruˇ siˇ c, On vertex symmetric digraphs,Discrete Math.36(1981), 69–81

    work page 1981

  21. [21]

    Pisanski, A classification of cubic bicirculants,Discrete Math.307(2007), 567–578

    T. Pisanski, A classification of cubic bicirculants,Discrete Math.307(2007), 567–578

    work page 2007

  22. [22]

    Pisanski, B

    T. Pisanski, B. Servatius, Configurations from a graphical viewpoint.Birkh¨ auser Advanced Texts: Basler Lehrb¨ ucher.[Birkh¨ auser Advanced Texts: Basel Text- books]. Birkh¨ auser/Springer, New York, 2013

    work page 2013

  23. [23]

    Wilson, Rose window graphs,Ars

    S. Wilson, Rose window graphs,Ars. Math. Contemp.1(2008), 7–19. 26

    work page 2008