pith. sign in

arxiv: 2605.27241 · v1 · pith:O7XY7J4Anew · submitted 2026-05-26 · 🧮 math.CO · math.GR

Two Arc-Disjoint Hamiltonian Paths in Finite Two-Generated Abelian Cayley Digraphs

SangHyun Park This is my paper

Pith reviewed 2026-06-29 16:43 UTC · model grok-4.3

classification 🧮 math.CO math.GR
keywords Cayley digraphHamiltonian patharc-disjoint pathsabelian grouptwo generatorsdirected cycleCartesian product
0
0 comments X

The pith

Every directed Cayley digraph on a finite abelian group with two distinct nonzero generators has two arc-disjoint Hamiltonian paths.

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

The paper proves that every finite abelian group generated by two distinct nonzero elements yields a Cayley digraph containing two arc-disjoint Hamiltonian paths. This settles the finite abelian two-generator conjecture. Together with prior results on two-factor and four-or-more-factor cases, the work resolves the directed-cycle product conjecture for Cartesian products of directed cycles with any number of factors. A reader would care because the paths model independent traversals in symmetric directed networks whose underlying structure is an abelian group.

Core claim

The central claim is that for any finite abelian group G and distinct nonzero generators a and b, the Cayley digraph Cay(G; a, b) contains two arc-disjoint Hamiltonian paths. The argument reduces the general case to cyclic groups, establishes a cut-reflection theorem asserting that the distance between the set Z of Hamiltonian cut values and its reflection N-Z is at most one in the family Cay(Z_k; a, a+1), and treats the remaining cyclic family via an explicit quotient-fiber construction while also settling the three-factor case for products of directed cycles.

What carries the argument

The cut-reflection theorem for Hamiltonian cut values in Cay(Z_k; a, a+1), which states that dist(Z, N-Z) <= 1 where Z is the set of such values and N = k-1.

If this is right

  • The directed-cycle product conjecture holds for Cartesian products with any number of factors.
  • The three-factor case for Cartesian products of directed cycles is proved.
  • The remaining cyclic family Cay(Z_k; -a, a+1) admits two arc-disjoint Hamiltonian paths via the quotient-fiber construction.
  • The two-generator conjecture is settled in full for all finite abelian groups.

Where Pith is reading between the lines

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

  • The reflection-distance bound may extend directly to non-cyclic abelian groups without first reducing to the cyclic case.
  • Sector-filling inequalities could be adapted to bound cut values in other families of Cayley digraphs on cyclic groups.
  • Small-order exhaustive search on even and odd k would independently verify the parity distinction between exact reflection and distance one.

Load-bearing premise

The cut-reflection theorem holds for Hamiltonian cut values in Cay(Z_k; a, a+1), specifically that dist(Z, N-Z) <=1.

What would settle it

A concrete counterexample would be any finite abelian group G with two distinct nonzero generators a and b such that Cay(G; a, b) contains no pair of arc-disjoint Hamiltonian paths, or a cyclic instance Cay(Z_k; a, a+1) in which the distance between Z and N-Z exceeds 1.

Figures

Figures reproduced from arXiv: 2605.27241 by Sanghyun Park.

Figure 1
Figure 1. Figure 1: The sector-filling injection. Points rR + sS with r/p + s/q ≤ 1 lie in the open sector between R and S and below the boundary of T. Proof. Since H(R) = p and H(S) = q, we have L(R) ≤ N p , L(S) ≤ N q . For r, s > 0, the lattice point Vr,s = rR + sS lies in the open sector between R and S. If r/p + s/q ≤ 1, then L(Vr,s) = rL(R) + sL(S) ≤ N  r p + s q  ≤ N. Since the opposite side of T is the line L = mn =… view at source ↗
Figure 2
Figure 2. Figure 2: Propagation across a δ-gap: if zi +zj = N −δ and zi+1 −zi = 2δ, then zi+1 +zj = N +δ. When the equality λi = δ fails, the extension is blocked; these blocked sides are the cases considered in Lemma 3.33. Definition 3.11 (δ-cores and blocking conditions). An internal gap [zt , zt+1] has δ-core, or δ-interior, [zt + δ, zt+1 − δ], which is nonempty when λt ≥ δ. The left endpoint cap has δ-core [0, cL − δ] if … view at source ↗
Figure 3
Figure 3. Figure 3: Schematic endpoint sector for cL = 2. When an endpoint ray has multiplicity two, the two families C + tR and 2C + tR give the sharpened lower bound used in Lemma 3.26. The endpoint cap of multiplicity two requires a sharper boundary estimate. Counting both columns C + tR and 2C + tR gives the needed strengthening. In the exceptional alignment N = 4α − 2, the second endpoint column meets the boundary in exa… view at source ↗
Figure 4
Figure 4. Figure 4: The Hamiltonian cut values Z = {1, 3, 5} for −−→Cay(Z10; 4, 5) and their reflection N − Z = {8, 6, 4} with N = 9. 30 [PITH_FULL_IMAGE:figures/full_fig_p030_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Quotient-fiber view of the second cyclic family. Both generators advance one step in [PITH_FULL_IMAGE:figures/full_fig_p032_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Layer pattern in the strong switchable lifting. The two Hamiltonian paths alternate [PITH_FULL_IMAGE:figures/full_fig_p034_6.png] view at source ↗
read the original abstract

We prove the finite abelian two-generator conjecture of Darijani--Miraftab--Witte Morris: every directed Cayley digraph on a finite abelian group with two distinct nonzero generators has two arc-disjoint Hamiltonian paths. The proof uses a cut-reflection theorem for Hamiltonian cut values in the family Cay(Z_k; a, a+1): if Z is the set of such values and N=k-1, then, with N-Z={N-z : z in Z}, dist(Z,N-Z)<=1. The proof uses sector-filling inequalities for primitive-ray multiplicities and an extremal graph recording pairs at minimal reflected distance. The estimate is sharp modulo parity: exact reflection occurs for odd k, while distance one occurs for even k. The second remaining cyclic family, Cay(Z_k; -a, a+1), is treated by an explicit quotient--fiber construction. We also prove the remaining three-factor case for Cartesian products of directed cycles. Together with the two-factor and at-least-four-factor theorems of Darijani--Miraftab--Witte Morris, this resolves their directed-cycle product conjecture for all numbers of factors.

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

1 major / 2 minor

Summary. The manuscript proves the finite abelian two-generator conjecture of Darijani--Miraftab--Witte Morris: every directed Cayley digraph on a finite abelian group with two distinct nonzero generators has two arc-disjoint Hamiltonian paths. The proof reduces to the cyclic families Cay(Z_k; a, a+1) and Cay(Z_k; -a, a+1). For the first it establishes a cut-reflection theorem asserting dist(Z, N-Z) ≤ 1 (N = k-1) via sector-filling inequalities on primitive-ray multiplicities together with an extremal graph on minimal reflected distances; the second family is handled by an explicit quotient-fiber construction. The three-factor Cartesian product case for directed cycles is also proved, completing the directed-cycle product conjecture when combined with prior two-factor and at-least-four-factor results.

Significance. If correct, the result resolves a long-standing conjecture in the theory of Hamiltonian paths in Cayley digraphs and completes the directed-cycle product conjecture for every number of factors. The cut-reflection theorem and the associated extremal-graph construction constitute new technical tools for controlling Hamiltonian cuts in cyclic groups; the quotient-fiber argument supplies an explicit reduction that may be reusable. The proof is parameter-free and supplies explicit constructions rather than existence via probabilistic or asymptotic methods.

major comments (1)
  1. [Cut-reflection theorem for Cay(Z_k; a, a+1)] The cut-reflection theorem (the claim that dist(Z, N-Z) ≤ 1 for Cay(Z_k; a, a+1)) is load-bearing for the entire two-generator reduction. The bound is derived from sector-filling inequalities on primitive-ray multiplicities and an extremal graph recording pairs at minimal reflected distance. The manuscript must verify that these inequalities admit no exceptions for any a and k (especially even k, where distance exactly 1 is asserted) and that the extremal graph captures every minimal-distance pair; an exception would falsify the distance bound and collapse the existence of two arc-disjoint paths for the corresponding digraphs.
minor comments (2)
  1. [Introduction / statement of main theorem] Clarify the precise definition of the set Z of Hamiltonian cut values and the reflected set N-Z at the first appearance of the cut-reflection statement.
  2. [Cyclic case Cay(Z_k; a, a+1)] Add a small table or explicit computation for small even k (e.g., k=6,8) showing that the distance is exactly 1, to illustrate sharpness.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive assessment of the result's significance and for identifying the load-bearing role of the cut-reflection theorem. We address the major comment below.

read point-by-point responses

  1. Referee: [Cut-reflection theorem for Cay(Z_k; a, a+1)] The cut-reflection theorem (the claim that dist(Z, N-Z) ≤ 1 for Cay(Z_k; a, a+1)) is load-bearing for the entire two-generator reduction. The bound is derived from sector-filling inequalities on primitive-ray multiplicities and an extremal graph recording pairs at minimal reflected distance. The manuscript must verify that these inequalities admit no exceptions for any a and k (especially even k, where distance exactly 1 is asserted) and that the extremal graph captures every minimal-distance pair; an exception would falsify the distance bound and collapse the existence of two arc-disjoint paths for the corresponding digraphs.

    Authors: The proof of the cut-reflection theorem (Theorem 3.1) establishes the bound by first deriving the sector-filling inequalities directly from the cyclic ordering of elements and the multiplicity counts of primitive rays in each angular sector. It then proceeds by contradiction: any configuration with dist(Z, N-Z) > 1 (or >1 for even k) produces a strict violation of at least one multiplicity inequality. The extremal graph is defined to contain every pair of elements realizing the minimal reflected distance under the given generators, so its properties apply to all such pairs by construction. The argument is exhaustive over residue classes of a modulo k and separates the odd-k (exact reflection) and even-k (distance exactly 1) cases; no additional case analysis is required. Consequently the verification is already contained in the existing proof and no exceptions arise. revision: no

Circularity Check

0 steps flagged

No significant circularity; proof constructs cut-reflection theorem from sector-filling inequalities

full rationale

The paper proves the two-generator conjecture by establishing a cut-reflection theorem for Cay(Z_k; a, a+1) via sector-filling inequalities on primitive-ray multiplicities and an extremal graph on minimal reflected distances; the distance bound dist(Z, N-Z) <= 1 is derived as a consequence rather than presupposed. The second family uses an explicit quotient-fiber construction. No steps reduce the central claim to a parameter fitted inside the paper, a self-citation chain, or a definition that imports the result. The derivation is self-contained against external benchmarks and does not match any enumerated circularity pattern.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The abstract invokes only standard properties of finite abelian groups and Cayley digraphs; no free parameters, invented entities, or ad-hoc axioms are mentioned.

axioms (2)
  • standard math Finite abelian groups are commutative and every element has finite order.
    Required to define the vertex set and the action of the two generators in the Cayley digraph.
  • domain assumption Cayley digraphs on groups are vertex-transitive.
    Used implicitly when discussing Hamiltonian paths that exist uniformly across the graph.

pith-pipeline@v0.9.1-grok · 5730 in / 1375 out tokens · 75181 ms · 2026-06-29T16:43:54.598503+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

19 extracted references · 3 canonical work pages

  1. [1]

    Alspach, J.-C

    B. Alspach, J.-C. Bermond, and D. Sotteau, Decomposition into cycles I: Hamilton decom- positions, inCycles and Rays, NATO ASI Series C, vol. 301, Kluwer, Dordrecht, 1990, pp. 9–18

    1990

  2. [2]

    Bermond, O

    J.-C. Bermond, O. Favaron, and M. Maheo, Hamiltonian decomposition of Cayley graphs of degree 4,Journal of Combinatorial Theory, Series B46 (1989), no. 2, 142–153

    1989

  3. [3]

    S. J. Curran and D. Witte, Hamilton paths in Cartesian products of directed cycles,Annals of Discrete Mathematics27 (1985), 35–74

    1985

  4. [4]

    S. J. Curran and J. A. Gallian, Hamiltonian cycles and paths in Cayley graphs and digraphs— a survey,Discrete Mathematics156 (1996), 1–18

    1996

  5. [5]

    Darijani, B

    I. Darijani, B. Miraftab, and D. Witte Morris, Arc-disjoint Hamiltonian paths in Cartesian products of directed cycles,Ars Mathematica Contemporanea25 (2025), no. 2, Paper #P2.10, doi:10.26493/1855-3974.3047.c2d

    work page doi:10.26493/1855-3974.3047.c2d 2025

  6. [6]

    M. F. Foregger, Hamiltonian decompositions of products of cycles,Discrete Mathematics24 (1978), 251–260

    1978

  7. [7]

    Housman, Enumeration of Hamiltonian paths in Cayley diagrams,Aequationes Mathe- maticae23 (1981), 80–97

    D. Housman, Enumeration of Hamiltonian paths in Cayley diagrams,Aequationes Mathe- maticae23 (1981), 80–97

    1981

  8. [8]

    D. S. Jungreis, Hamiltonian paths in Cayley digraphs of finitely generated infinite abelian groups,Discrete Mathematics78 (1989), no. 1–2, 95–104, doi:10.1016/0012-365X(89)90165-9

    work page doi:10.1016/0012-365x(89)90165-9 1989

  9. [9]

    G. H. J. Lanel, H. K. Pallage, J. K. Ratnayake, S. Thevasha, and B. A. K. Welihinda, A survey on Hamiltonicity in Cayley graphs and digraphs on different groups,Discrete Mathematics, Algorithms and Applications11 (2019), no. 5, 1930002

    2019

  10. [10]

    Lov´ asz, Problem 11, inCombinatorial Structures and their Applications, Gordon and Breach, New York, 1970, p

    L. Lov´ asz, Problem 11, inCombinatorial Structures and their Applications, Gordon and Breach, New York, 1970, p. 243

    1970

  11. [11]

    Liu, Hamiltonian decompositions of Cayley graphs on abelian groups,Journal of Combi- natorial Theory, Series B88 (2003), no

    J. Liu, Hamiltonian decompositions of Cayley graphs on abelian groups,Journal of Combi- natorial Theory, Series B88 (2003), no. 2, 305–321. 39

    2003

  12. [12]

    Witte Morris, 2-generated Cayley digraphs on nilpotent groups have Hamiltonian paths, Contributions to Discrete Mathematics7 (2012), no

    D. Witte Morris, 2-generated Cayley digraphs on nilpotent groups have Hamiltonian paths, Contributions to Discrete Mathematics7 (2012), no. 1, 41–47

    2012

  13. [13]

    Pak and R

    I. Pak and R. Radoiˇ ci´ c, Hamiltonian paths in Cayley graphs,Discrete Mathematics309 (2009), 5501–5508

    2009

  14. [14]

    Stong, Hamilton decompositions of Cartesian products of graphs,Discrete Mathematics 90 (1991), 169–190

    R. Stong, Hamilton decompositions of Cartesian products of graphs,Discrete Mathematics 90 (1991), 169–190

    1991

  15. [15]

    T. W. Tillson, A Hamiltonian decomposition of K∗ 2m, 2m≥ 8,Journal of Combinatorial Theory, Series B29 (1980), no. 1, 68–74

    1980

  16. [16]

    W. T. Trotter, Jr. and P. Erd˝ os, When the Cartesian product of directed cycles is Hamiltonian, Journal of Graph Theory2 (1978), no. 2, 137–142

    1978

  17. [17]

    Witte Morris, On Cayley digraphs that do not have Hamiltonian paths,International Journal of Combinatorics2013, Article ID 725809, 7 pp., doi:10.1155/2013/725809

    D. Witte Morris, On Cayley digraphs that do not have Hamiltonian paths,International Journal of Combinatorics2013, Article ID 725809, 7 pp., doi:10.1155/2013/725809

    work page doi:10.1155/2013/725809 2013

  18. [18]

    Witte, On Hamiltonian circuits in Cayley diagrams,Discrete Mathematics38 (1982), no

    D. Witte, On Hamiltonian circuits in Cayley diagrams,Discrete Mathematics38 (1982), no. 1, 99–108

    1982

  19. [19]

    Witte and J

    D. Witte and J. A. Gallian, A survey: Hamiltonian cycles in Cayley graphs,Discrete Mathematics51 (1984), 293–304. 40

    1984