Symmetry classes of Hamiltonian cycles

(2) Universit\"at Leipzig; (3) Technische Universit\"at Darmstadt); Annette Lutz (3); Julia Baligacs (1); Lena Volk (3) ((1) University of Oxford; Sofia Brenner (2)

arxiv: 2506.21337 · v2 · submitted 2025-06-26 · 🧮 math.CO · cs.DM

Symmetry classes of Hamiltonian cycles

Julia Baligacs (1) , Sofia Brenner (2) , Annette Lutz (3) , Lena Volk (3) ((1) University of Oxford , (2) Universit\"at Leipzig , (3) Technische Universit\"at Darmstadt) This is my paper

Pith reviewed 2026-05-19 07:53 UTC · model grok-4.3

classification 🧮 math.CO cs.DM MSC 05C4505C25

keywords Hamiltonian cyclesCayley graphsabelian groupsgraph automorphismsCartesian productsHamiltonian-transitive graphssymmetry classes

0 comments

The pith

Cayley graphs of abelian groups are not Hamiltonian-transitive under mild conditions, so they contain at least two Hamiltonian cycles with no automorphism mapping one to the other.

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

The paper studies Hamiltonian cycles in graphs up to the symmetries given by the graph's own automorphisms. It focuses on the extreme case of Hamiltonian-transitive graphs, where every pair of Hamiltonian cycles can be mapped onto each other by some automorphism. The central result shows that Cayley graphs built from abelian groups fail this property except in a few unsurprising cases, which means they always have at least two distinct symmetry classes of Hamiltonian cycles. To reach this conclusion the authors reduce the question of Hamiltonian-transitivity to simpler questions about the prime factors that appear in the Cartesian product decomposition of the graph. They also give constructions of regular graphs that are Hamiltonian-transitive and of other families that realize many distinct symmetry classes.

Core claim

Cayley graphs of abelian groups are not Hamiltonian-transitive (under some mild conditions and some non-surprising exceptions), i.e., they contain at least two structurally different Hamiltonian cycles. This is proved by reducing Hamiltonian-transitivity to properties of the prime factors of a Cartesian product decomposition of the graph.

What carries the argument

The reduction of Hamiltonian-transitivity to the properties of the prime factors appearing in the Cartesian product decomposition of the graph.

If this is right

Cayley graphs of abelian groups possess at least two distinct symmetry classes of Hamiltonian cycles.
Checking Hamiltonian-transitivity reduces to examining the prime Cartesian factors of the graph.
There exist infinite families of regular graphs that are Hamiltonian-transitive.
There exist families of graphs that realize arbitrarily many distinct symmetry classes of Hamiltonian cycles.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same reduction technique may help classify Hamiltonian-transitivity in other families of vertex-transitive graphs.
Algorithms that enumerate Hamiltonian cycles could first compute the Cartesian prime factorization to avoid redundant symmetry checks.
Uniquely Hamiltonian graphs up to symmetry are likely to be rare outside specially constructed examples.

Load-bearing premise

The reduction of Hamiltonian-transitivity to properties of the prime factors of the Cartesian product decomposition holds for the Cayley graphs and groups under consideration.

What would settle it

A single Cayley graph on an abelian group that satisfies the stated mild conditions yet admits an automorphism taking any Hamiltonian cycle to any other would falsify the main claim.

read the original abstract

We initiate the study of Hamiltonian cycles up to symmetries of the underlying graph. Our focus lies on the extremal case of Hamiltonian-transitive graphs, i.e., Hamiltonian graphs where, for every pair of Hamiltonian cycles, there is a graph automorphism mapping one cycle to the other. This generalizes the extensively studied uniquely Hamiltonian graphs. In this paper, we show that Cayley graphs of abelian groups are not Hamiltonian-transitive (under some mild conditions and some non-surprising exceptions), i.e., they contain at least two structurally different Hamiltonian cycles. To show this, we reduce Hamiltonian-transitivity to properties of the prime factors of a Cartesian product decomposition, which we believe is interesting in its own right. We complement our results by constructing infinite families of regular Hamiltonian-transitive graphs and take a look at the opposite extremal case by constructing a family with many different Hamiltonian cycles up to symmetry.

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.

Desk Editor's Note private letter to a colleague

The paper defines Hamiltonian-transitive graphs and shows abelian Cayley graphs usually have multiple symmetry classes of Ham cycles via a Cartesian reduction, with explicit constructions on both sides.

read the letter

The punchline is that this paper defines Hamiltonian-transitive graphs—those where the automorphism group acts transitively on Hamiltonian cycles—and proves that Cayley graphs on abelian groups are not Hamiltonian-transitive under mild conditions, so they have at least two distinct symmetry classes. The proof goes through a reduction of the property to the prime factors of the graph's Cartesian product decomposition, and the authors supply infinite families that are Hamiltonian-transitive plus families with many distinct classes. That reduction and the two families of constructions are the genuinely new pieces. The Cartesian-product angle is a clean way to exploit the structure of these graphs, and the constructions are explicit enough that they can be checked directly. The non-transitivity claim for abelian Cayley graphs follows from the reduction plus the known factorizations, which is a reasonable route. The soft spot is whether the reduction fully tracks the automorphism group. Cayley graphs on abelian groups can admit extra automorphisms that are not just left translations, and if any of those mix cycles across different prime factors, the orbit count could drop. The paper invokes mild conditions and exceptions to rule this out, but that step is load-bearing and would need to be inspected line by line to confirm no mixing cases slip through. Overall the argument is coherent on its own terms and the constructions give independent evidence that the property behaves as claimed in some cases. This is for combinatorial graph theorists who work on Hamiltonicity, vertex-transitive graphs, or Cayley graphs. A reader who already knows unique Hamiltonicity or Cartesian products will see how to extend the ideas. It deserves a serious referee because the claims are concrete, the reduction is checkable, and the constructions are reproducible.

Referee Report

2 major / 2 minor

Summary. The paper initiates the study of Hamiltonian cycles up to graph automorphisms, defining Hamiltonian-transitive graphs as those in which Aut(G) acts transitively on the set of all Hamiltonian cycles. It claims that Cayley graphs Cay(Γ, S) on abelian groups Γ are not Hamiltonian-transitive (under mild conditions on Γ and S, with some explicit exceptions), by reducing the transitivity property to the structure of the prime-power factors in a Cartesian-product decomposition of the graph. The work is complemented by explicit constructions of infinite families of regular Hamiltonian-transitive graphs and of graphs possessing many distinct symmetry classes of Hamiltonian cycles.

Significance. If the reduction is correct, the result supplies a structural criterion that distinguishes symmetry classes of Hamiltonian cycles in an important family of vertex-transitive graphs and generalizes the theory of uniquely Hamiltonian graphs. The reduction to Cartesian factors may prove reusable for other automorphism-related properties, while the two families of constructions furnish concrete examples at opposite extremes of the spectrum of possible numbers of symmetry classes.

major comments (2)

[Reduction to Cartesian factors] The reduction of Hamiltonian-transitivity to properties of the prime factors of the Cartesian-product decomposition (described in the abstract and presumably detailed in the main technical section) must explicitly account for the full automorphism group of the Cayley graph, including any additional symmetries induced by S that could mix cycles across distinct prime-power factors. If such mixing automorphisms exist and are not ruled out by the mild conditions, the claimed existence of at least two distinct symmetry classes does not follow.
[Main theorem on abelian Cayley graphs] The precise statement of the 'mild conditions' on the abelian group Γ and connection set S is load-bearing for the main theorem; these conditions must be shown to exclude precisely the cases in which the automorphism group could act transitively on Hamiltonian cycles, and the manuscript should verify that the reduction still applies when the generating set is not a minimal connection set.

minor comments (2)

[Preliminaries] Notation for the Cartesian-product decomposition and the induced action on Hamiltonian cycles should be introduced with a short example before the general argument.
[Constructions] The constructions of the Hamiltonian-transitive families and the high-symmetry-class families would benefit from a table summarizing the parameters (order, degree, number of symmetry classes) for the first few members of each family.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their thorough review and valuable suggestions. The points raised regarding the explicit handling of the full automorphism group and the precise statement of the mild conditions are well-taken. We address each comment in turn and will make revisions to clarify these aspects in the manuscript.

read point-by-point responses

Referee: [Reduction to Cartesian factors] The reduction of Hamiltonian-transitivity to properties of the prime factors of the Cartesian-product decomposition (described in the abstract and presumably detailed in the main technical section) must explicitly account for the full automorphism group of the Cayley graph, including any additional symmetries induced by S that could mix cycles across distinct prime-power factors. If such mixing automorphisms exist and are not ruled out by the mild conditions, the claimed existence of at least two distinct symmetry classes does not follow.

Authors: We agree that this aspect requires more explicit treatment to ensure the argument is complete. In the current manuscript, the reduction relies on the structure of the Cartesian product and the fact that automorphisms of Cayley graphs on abelian groups preserve the group structure in a way that respects the prime-power decomposition under the mild conditions. However, to directly address the possibility of mixing symmetries induced by S, we will add a new lemma in the revised version that shows that any automorphism of the Cayley graph either acts within the factors or is excluded by our conditions on S (specifically, that S is such that it does not connect different prime-power components in a mixing way). This will confirm that the transitivity would imply transitivity on the factors, leading to the existence of at least two classes when the factors are not transitive. We believe this strengthens the proof without altering the main results. revision: yes
Referee: [Main theorem on abelian Cayley graphs] The precise statement of the 'mild conditions' on the abelian group Γ and connection set S is load-bearing for the main theorem; these conditions must be shown to exclude precisely the cases in which the automorphism group could act transitively on Hamiltonian cycles, and the manuscript should verify that the reduction still applies when the generating set is not a minimal connection set.

Authors: The referee is correct that the mild conditions need to be stated more precisely and their role in excluding transitivity cases clarified. In the revision, we will provide an explicit list of the conditions in the statement of the main theorem: Γ is a finite abelian group of order greater than 2, S is a symmetric generating set not containing the identity, and the graph is not a cycle or complete graph (the exceptions). We will include a proof or reference showing that these exclude the transitive cases by ensuring the Cartesian factors have distinct properties or multiple cycle types. Additionally, we will verify in a remark that the reduction to prime factors holds independently of whether S is minimal, as the decomposition is based on the group Γ being abelian and the resulting graph structure, not on the size of S. This verification will be added to the technical section. revision: yes

Circularity Check

0 steps flagged

No circularity; result follows from reduction to Cartesian factors and explicit constructions

full rationale

The paper derives its central claim by reducing Hamiltonian-transitivity of Cayley graphs on abelian groups to properties of the prime factors in their Cartesian product decomposition. This reduction is presented as an independent technical contribution, supported by explicit constructions of infinite families and analysis of automorphism groups. No step defines the target property in terms of itself, renames a fitted quantity as a prediction, or relies on a load-bearing self-citation whose content is unverified. The derivation remains self-contained against external graph-theoretic benchmarks such as known facts about Cartesian products and Cayley graph automorphisms.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work relies on standard background results from graph theory; no free parameters, new entities, or ad-hoc axioms are introduced in the abstract.

axioms (1)

standard math Standard facts about graph automorphisms, Hamiltonian cycles, and the prime-factor decomposition of Cartesian products of graphs.
The reduction of Hamiltonian-transitivity is stated to rest on these background properties.

pith-pipeline@v0.9.0 · 5707 in / 1185 out tokens · 34424 ms · 2026-05-19T07:53:57.737705+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Cayley graphs of abelian groups ... contain at least two structurally different Hamiltonian cycles (Theorems 2–3)

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.