pith. sign in

arxiv: 2606.21941 · v1 · pith:GAGKOBDQnew · submitted 2026-06-20 · 🧮 math.CO

Computing the Hamiltonian compression factors of cubic graphs

Marston Conder , Gregor Potocnik , Primoz Potocnik This is my paper

Pith reviewed 2026-06-26 11:56 UTC · model grok-4.3

classification 🧮 math.CO
keywords Hamiltonian cyclescubic graphsedge-transitive graphsautomorphismscompression factorLCF codesalgorithmgraph symmetry
0
0 comments X

The pith

An algorithm computes the Hamiltonian compression factor, the largest rotational automorphism order preserving a Hamiltonian cycle, for cubic edge-transitive graphs up to 10,000 vertices.

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

The paper develops an algorithm designed to identify Hamiltonian cycles that are invariant under a graph automorphism acting as a rotation. This algorithm is then used to calculate the Hamiltonian compression factor for every cubic edge-transitive graph with at most 10,000 vertices. Exact values are obtained for all but two non-Hamiltonian graphs and 98 others, for which lower bounds are provided instead. The work also yields the shortest LCF codes for these graphs as a byproduct. Readers interested in graph symmetries would find value in having concrete data on rotational symmetries of cycles in a complete list of small symmetric cubic graphs.

Core claim

The authors claim that their algorithm successfully computes the Hamiltonian compression factors of all cubic edge-transitive graphs on up to 10,000 vertices except two non-Hamiltonian ones, giving exact values in most cases and lower bounds for 98 graphs, while also producing shortest LCF codes for each.

What carries the argument

The algorithm for computing Hamiltonian cycles invariant under a rotational automorphism, which determines the largest order of such an automorphism.

If this is right

  • The Hamiltonian compression factor is now known exactly for the great majority of cubic edge-transitive graphs with up to 10,000 vertices.
  • Shortest LCF codes are determined for all Hamiltonian graphs in this class.
  • Lower bounds on the compression factor are established for 98 graphs, the smallest with 2304 vertices.
  • Two graphs are confirmed to have no Hamiltonian cycle.

Where Pith is reading between the lines

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

  • The results could serve as a benchmark for testing new algorithms on larger or different graph classes.
  • Knowing these factors might help in understanding the relationship between edge-transitivity and Hamiltonian properties in cubic graphs.
  • If extended, the approach might apply to finding other types of symmetric cycles in graphs.

Load-bearing premise

The algorithm correctly finds the largest order of an automorphism that preserves a Hamiltonian cycle and rotates on it, assuming the input collection of all cubic edge-transitive graphs is complete and accurate.

What would settle it

Finding a cubic edge-transitive graph on at most 10,000 vertices missing from the computation, or discovering a Hamiltonian cycle with a higher rotational order in one of the 98 graphs than the reported lower bound.

Figures

Figures reproduced from arXiv: 2606.21941 by Gregor Potocnik, Marston Conder, Primoz Potocnik.

Figure 1
Figure 1. Figure 1: The Hamiltonian compression factor κ of each graph plotted against its order n, for cubic arc-transitive graphs (left) and cubic semisymmetric graphs (right). Each dot is one graph; the dashed rays are the lines κ = n/p for the indicated periods p. Note the different vertical scales, and that no semisymmetric graph lies above the ray κ = n/6. compression factor, and [PITH_FULL_IMAGE:figures/full_fig_p009_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: The average Hamiltonian compression factor [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: The average relative Hamiltonian compression factor [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
read the original abstract

We present an algorithm for computing Hamiltonian cycles that are invariant under a graph automorphism acting on them as a rotation. We also present an application of this algorithm for computing the Hamiltonian compression factor of a graph, that is, the largest order of an automorphism preserving some Hamiltonian cycle and acting on it as a rotation. As an example, we compute the Hamiltonian compression factors of all cubic edge-transitive graphs on up to $10{,}000$ vertices, with the exception of two graphs, which are not Hamiltonian, and $98$ graphs (the smallest having $2304$ vertices) for which only a lower bound for the compression factor is given. As a byproduct, we obtain shortest LCF codes for each of these graphs (except for the two non-Hamiltonian ones; for the $98$ unresolved graphs, the codes obtained are the shortest among those we found).

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

2 major / 1 minor

Summary. The paper presents an algorithm for computing Hamiltonian cycles invariant under a graph automorphism that acts as a rotation on the cycle. It applies this to compute the Hamiltonian compression factor (largest order of such an automorphism) for all cubic edge-transitive graphs on at most 10,000 vertices, reporting exact values except for two non-Hamiltonian graphs and 98 graphs (smallest 2304 vertices) where only lower bounds are obtained. Shortest LCF codes are obtained as a byproduct for the resolved cases.

Significance. If the algorithm is correct and the input list of graphs is complete, the work provides a large-scale computational enumeration of Hamiltonian compression factors in cubic edge-transitive graphs, together with explicit lower bounds and LCF codes. This constitutes a concrete data point for the field and could support further theoretical work on rotational symmetries of Hamiltonian cycles. The explicit flagging of the two non-Hamiltonian graphs and the 98 unresolved cases is a positive feature.

major comments (2)
  1. [Abstract (algorithm description)] The manuscript states that an algorithm is presented for finding rotationally invariant Hamiltonian cycles, but provides no pseudocode, complexity analysis, or verification on small known graphs (e.g., the Petersen graph or other cubic edge-transitive graphs with known compression factors). This detail is load-bearing for assessing the reliability of the exact values and lower bounds reported for graphs up to 10,000 vertices.
  2. [Abstract (application to graph list)] The input list of cubic edge-transitive graphs is described as external and complete, yet no reference, citation, or verification step is given confirming that the classification up to 10,000 vertices matches the current state of the literature or that the two non-Hamiltonian exceptions were independently confirmed.
minor comments (1)
  1. [Abstract] The abstract mentions 'shortest LCF codes' as a byproduct but does not clarify the precise definition of 'shortest' used or how ties are broken when multiple codes of the same length exist.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their constructive comments. We address each major comment below and will revise the manuscript accordingly to improve clarity and verifiability.

read point-by-point responses

  1. Referee: [Abstract (algorithm description)] The manuscript states that an algorithm is presented for finding rotationally invariant Hamiltonian cycles, but provides no pseudocode, complexity analysis, or verification on small known graphs (e.g., the Petersen graph or other cubic edge-transitive graphs with known compression factors). This detail is load-bearing for assessing the reliability of the exact values and lower bounds reported for graphs up to 10,000 vertices.

    Authors: We agree that the current manuscript provides insufficient detail on the algorithm for independent assessment. In the revised version we will add explicit pseudocode, a complexity analysis, and verification results on small graphs including the Petersen graph (where the compression factor is 5) and other known cubic edge-transitive graphs with established values. revision: yes

  2. Referee: [Abstract (application to graph list)] The input list of cubic edge-transitive graphs is described as external and complete, yet no reference, citation, or verification step is given confirming that the classification up to 10,000 vertices matches the current state of the literature or that the two non-Hamiltonian exceptions were independently confirmed.

    Authors: We acknowledge the absence of a specific citation or verification statement for the graph list. The revised manuscript will include a reference to the source of the complete enumeration of cubic edge-transitive graphs and a note confirming the two non-Hamiltonian exceptions via independent literature results. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper presents a search algorithm that enumerates Hamiltonian cycles fixed by rotational automorphisms of maximal order and applies it directly to an external, pre-classified list of cubic edge-transitive graphs. All reported compression factors (or lower bounds) are explicit outputs of this enumeration; no parameters are fitted to the target values, no quantity is defined in terms of itself, and no load-bearing step reduces to a self-citation or ansatz imported from the authors' prior work. The two non-Hamiltonian exceptions and the 98 unresolved cases are explicitly flagged, confirming that the derivation chain remains self-contained against external graph data.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard definitions from graph theory together with the correctness of the new search algorithm; no free parameters, invented entities, or ad-hoc axioms are introduced in the abstract.

axioms (2)
  • standard math Cubic graphs are 3-regular graphs whose automorphism groups act transitively on edges.
    Standard background assumption in the field of symmetric graphs.
  • domain assumption The listed graphs up to 10,000 vertices exhaust the cubic edge-transitive graphs in that range.
    The computation scope depends on an external enumeration of all such graphs.

pith-pipeline@v0.9.1-grok · 5676 in / 1296 out tokens · 53085 ms · 2026-06-26T11:56:09.753549+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

18 extracted references · 1 canonical work pages

  1. [1]

    Bosma, J

    W. Bosma, J. Cannon, C. Playoust, The Magma algebra system. I. The user language, J. Sym- bolic Comp.24(1997), 235–265

    1997

  2. [2]

    Bouwer (ed.),The Foster Census, Charles Babbage Research Centre, Winnipeg, 1988

    I.Z. Bouwer (ed.),The Foster Census, Charles Babbage Research Centre, Winnipeg, 1988

    1988

  3. [3]

    Conder, Trivalent (cubic) symmetric graphs on up to 10000 vertices,https://www.math

    M. Conder, Trivalent (cubic) symmetric graphs on up to 10000 vertices,https://www.math. auckland.ac.nz/~conder/symmcubic10000list.txt(accessed 12th June 2026)

    2026

  4. [4]

    Conder, Trivalent (cubic) semi-symmetric graphs on up to 10000 vertices,https://www

    M. Conder, Trivalent (cubic) semi-symmetric graphs on up to 10000 vertices,https://www. math.auckland.ac.nz/~conder/SemisymmCubic10000.txt(accessed 12th June 2026)

    2026

  5. [5]

    Algebra685(2026), 703–737

    M.ConderandP.Potočnik, Edge-transitivecubicgraphs: analysis, cataloguingandenumeration, J. Algebra685(2026), 703–737

    2026

  6. [6]

    Conder and P

    M. Conder and P. Potočnik, Census of cubic edge-transitive graphs,https://fostercensus. graphsym.net(accessed 17th May 2026)

    2026

  7. [7]

    Conder, P

    M. Conder, P. Potočnik, G. Potočnik,Census of cubic edge-transitive graphs and their optimal LCF codes, Zenodo (2026).https://doi.org/10.5281/zenodo.20609902

    work page doi:10.5281/zenodo.20609902 2026

  8. [8]

    Eppstein, The traveling salesman problem for cubic graphs,J

    D. Eppstein, The traveling salesman problem for cubic graphs,J. Graph Alg. Appl.11(2007), 61–81

    2007

  9. [9]

    Frucht, A canonical representation of trivalent Hamiltonian graphs,J

    R. Frucht, A canonical representation of trivalent Hamiltonian graphs,J. Graph Theory1(1977), 45–60

    1977

  10. [10]

    org(accessed 17th May 2026)

    The GAP Group, GAP – Groups, Algorithms, and Programming,https://www.gap-system. org(accessed 17th May 2026). 11

    2026

  11. [11]

    Goldschmidt, Automorphisms of trivalent graphs,Ann

    D. Goldschmidt, Automorphisms of trivalent graphs,Ann. Math.111(1980), 377–406

    1980

  12. [12]

    Gregor, A

    P. Gregor, A. Merino, T. Mütze, The Hamilton compression of highly symmetric graphs,Annals Combin.28(2024), 379–437

    2024

  13. [13]

    Kutnar, D

    K. Kutnar, D. Marušič, A. S. Razafimahatratra, Infinite families of vertex-transitive graphs with prescribed Hamilton compression,Annals Combin.28(2024), 1243–1255

    2024

  14. [14]

    McKay,Nauty package,https://pallini.di.uniroma1.it(accessed 17th May 2026)

    B. McKay,Nauty package,https://pallini.di.uniroma1.it(accessed 17th May 2026)

    2026

  15. [15]

    Potočnik, P

    P. Potočnik, P. Spiga, G. Verret, On the order of arc-stabilisers in arc-transitive graphs with prescribed local group,Trans. Amer. Math. Soc.366(2014), 3729–3745

    2014

  16. [16]

    Potočnik, P

    P. Potočnik, P. Spiga, G. Verret, Bounding the order of the vertex-stabiliser in3-valent vertex- transitive and4-valent arc-transitive graphs,J. Combin. Theory, Ser. B.111(2015), 148–180

    2015

  17. [17]

    Rubin, A search procedure for Hamilton paths and circuits,J

    F. Rubin, A search procedure for Hamilton paths and circuits,J. ACM21(1974), 576–580

    1974

  18. [18]

    Tutte, A family of cubical graphs,Proc

    W. Tutte, A family of cubical graphs,Proc. Cambridge Philos. Soc.43(1947), 459–474. 12

    1947