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

SangHyun Park · 2026

Read Two Arc-Disjoint Hamiltonian Paths in Finite Two-Generated Abelian Cayley Digraphs by SangHyun Park (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-27241.txt.

Introduction

SangHyun Park proves a conjecture about directed Cayley graphs on finite abelian groups with two generators. He shows every such graph holds two Hamiltonian paths that share no directed edge. The proof builds a cut reflection result for one cyclic family, treats a second family by an explicit construction, and closes the remaining product case.

Catalog record

CREATORSangHyun Park
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE93076
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.27241

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Two Arc-Disjoint Hamiltonian Paths in Finite Two-Generated Abelian Cayley Digraphs SangHyun Park 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 → ​ ( ℤ k , a , a + 1 ) \overrightarrow{\operatorname{Cay}}(\mathbb{Z}_{k};a,a+1) : if Z Z is the set of such values and N = k − 1 N=k-1 , then, with N − Z = { N − z : z ∈ Z } N-Z=\{N-z:z\in Z\} , dist ⁡ ( Z , N − Z ) ≤ 1 . \operatorname{dist}(Z,N-Z)\leq 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 k , while distance one occurs for even k k . The second remaining cyclic family, Cay → ​ ( ℤ k , − a , a + 1 ) \overrightarrow{\operatorname{Cay}}(\mathbb{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. 1 Introduction Hamiltonian paths and cycles in Cayley graphs are a central theme in algebraic graph theory. They are connected to Lovász’s question on Hamiltonian paths in vertex-transitive graphs [ 10 ] and to the Hamiltonian-cycle problems in Cayley graphs and digraphs surveyed in [ 19 , 4 ] . Hamilton decompositions of dense directed graphs begin with Tillson’s theorem for complete directed graphs [ 15 ] , while the decomposition theory for Cayley graphs includes the survey of Alspach–Bermond–Sotteau [ 1 ] , Stong’s work on Cartesian products [ 14 ] , and Liu’s Hamilton-decomposition theorem for abelian Cayley graphs [ 11 ] . These results concern decompositions into Hamiltonian cycles in dense or undirected settings; the problem considered here is a sparse directed packing problem, asking for two arc-disjoint Hamiltonian paths in a two-generated Cayley digraph. Directed Cayley graphs have their own difficulties: Hamiltonian cycles can fail even in small valence, and in nonabelian settings even Hamiltonian paths may fail. Positive and negative results for Cayley digraph Hamiltonian paths include Witte [ 18 ] , Jungreis [ 8 ] , Morris [ 12 , 17 ] , and the survey of Lanel, Pallage, Ratnayake, Thevasha, and Welihinda [ 9 ] . Related work on Cayley diagrams and products of directed cycles includes Bermond–Favaron–Mahéo [ 2 ] , Curran–Witte [ 3 ] , Foregger [ 6 ] , Housman [ 7 ] , and Pak–Radoičić [ 13 ] . For Cartesian products of directed cycles, Trotter–Erdős gave the two-factor Hamiltonicity characterization, and Curran–Witte proved Hamiltonicity for products of three or more nontrivial directed cycles [ 16 , 3 ] . Darijani–Miraftab–Witte Morris (abbreviated DMM below) reduced the finite abelian two-generator problem to two cyclic assertions [ 5 ] . They also settled Cartesian products of directed cycles with two factors and with at least four factors, leaving the three-factor product as the remaining case. We resolve these remaining cases: the family \overrightarrow{\operatorname{Cay}}(\mathbb{Z}_{k};a,a+1) is settled by a reflection theorem for Hamiltonian cut values, the family \overrightarrow{\operatorname{Cay}}(\mathbb{Z}_{k};-a,a+1) by a direct quotient–fiber construction, and the three-factor product by a switchable-pair lifting argument. Combining the two cyclic results below with the DMM reduction theorem gives the following theorem. Theorem 1.1 (Main theorem) . Let G be a finite abelian group, and let a,b\in G\setminus\{0\} be distinct elements that generate G . Then \overrightarrow{\operatorname{Cay}}(G;a,b) has two arc-disjoint Hamiltonian paths. The two-generator assumption is essentially the minimal valence condition: for |G|\geq 3 , a one-generator directed Cayley graph has only |G| non-loop arcs, fewer than the 2|G|-2 arcs required by two disjoint Hamiltonian paths. For |G|=2 the hypothesis is vacuous. DMM formulated this finite abelian two-generator statement as Conjecture 1.3 [ 5 , Conjecture 1.3] . Thus Theorem 1.1 gives the following immediate consequence. Corollary 1.2 . Conjecture 1.3 of Darijani–Miraftab–Witte Morris holds for all finite abelian groups. For finite subsets X,Y\subseteq\mathbb{Z} , we write \operatorname{dist}(X,Y)=\min\{|x-y|:x\in X,\ y\in Y\}. The central structural input is a reflection theorem for Hamiltonian cut values in the first cyclic family \overrightarrow{\operatorname{Cay}}(\mathbb{Z}_{k};a,a+1),\qquad a\not\equiv 0,-1\pmod{k}. The standard cut candidates in this family are parametrized by a cut value, and the Hamiltonian ones form a finite set Z\subseteq\{0,1,\ldots,k-1\} . The count criterion of DMM asks for d,e\in Z with d+e\in\{k-2,k-1,k\}. Writing N=k-1 , Theorem 3.34 proves the stronger structural estimate \operatorname{dist}(Z,N-Z)\leq 1. The DMM parametrization identifies Z with a slope-ordered multiplicity sequence of primitive rays. In this form the cut-reflection theorem may be viewed as a reflection principle for ordered primitive-ray multiplicity systems satisfying the endpoint identity and sector-filling inequalities. We prove the reflection estimate by showing that any reflected gap of width at least two would force, through sector filling, more intervening multiplicity than the corresponding extremal configuration permits. More concretely, if pairs at distance \delta\geq 2 are recorded in a reflected gap graph \Gamma_{\delta} , then each fully blocked extremal edge or loop is ruled out by the lower bound \Theta(p,q)=\#\left\{(r,s)\in\mathbb{Z}_{>0}^{2}:\frac{r}{p}+\frac{s}{q}\leq 1\right\} for the multiplicity between primitive rays of multiplicities p and q . A sharper boundary-ray estimate handles the last endpoint cap of multiplicity two. This is a near-antipodal pair statement: it asserts the existence of a reflected pair near the center, rather than a Hausdorff-type symmetry of the whole cut set. The estimate is sharp modulo parity: odd k gives exact reflection, while even k forces distance one; Example 3.36 shows the distance-one case. The second cyclic family is \overrightarrow{\operatorname{Cay}}(\mathbb{Z}_{k};-a,a+1),\qquad 2a+1\mid k, with distinct generators. Modulo 2a+1 , the two generators move in the same quotient direction. A quotient-position rule with a+2 positions assigned to the generator -a gives a Hamiltonian cycle with fiber shift -1 ; the complementary cycle cover has fiber shift +2 and is either Hamiltonian or splits into two cycles that can be spliced by one arc of the first cycle. We also prove the remaining three-factor case in the Cartesian-product problem for directed cycles. Darijani, Miraftab, and Witte Morris proved the two-factor case and the case of at least four factors, and treated several three-factor subcases. Theorem 1.3 proves the remaining three-factor case; combined with their two-factor and at-least-four-factor results, it gives Corollary 1.4 . The proof isolates a switchability condition that lifts a pair of disjoint Hamiltonian paths through one directed-cycle factor. Theorem 1.3 . For all m,n,\ell\geq 2 , the Cartesian product \vec{C}_{m}\mathbin{\square}\vec{C}_{n}\mathbin{\square}\vec{C}_{\ell} has two arc-disjoint Hamiltonian paths. Corollary 1.4 . For every r\geq 2 , the Cartesian product of r directed cycles of length at least two has two arc-disjoint Hamiltonian paths. In particular, Conjecture 1.1 of Darijani–Miraftab–Witte Morris holds. The proof of Corollary 1.4 is given at the end of Section 6 , after Theorem 1.3 is proved. Further directions are discussed after the proofs. 2 Preliminaries from Darijani–Miraftab–Witte Morris All groups are written additively. The directed Cayley digraph \overrightarrow{\operatorname{Cay}}(G;a,b) has vertex set G and arcs x\to x+a,\qquad x\to x+b\qquad(x\in G). If P is a path or

Read the complete text