Certified Euclidean-Residue Minimal-Alignment Switch Decompositions for Three Edge-Disjoint Hamiltonian Cycles in Eisenstein–Jacobi Networks arXiv:2606.19832v1 [cs.DC] 18 Jun 2026
Bader Albader Department of Computer Science, Faculty of Science, Kuwait University, Kuwait [email protected]
Abstract Eisenstein–Jacobi (EJ) networks are degree-six quotient-lattice interconnection networks. For a generator α = a + bρ, let N = a2 + ab + b2 and d = gcd(a, b). If d = 1, the three natural unit directions already give three edge-disjoint Hamiltonian cycles. If d > 1, each unit direction splits into d cycles and the EDHC problem becomes a cycle-splicing problem. Existing non-coprime EJ decompositions prove existence by using a rectangular representation and exchange schedules. This paper develops a different, local switch calculus in the natural Cayley geometry. The first two Hamiltonian cycles are built using the minimum possible d − 1 intercomponent switches each, and the third factor is obtained as the unused edge complement. The contribution is deliberately not a new existence theorem for all non-coprime EJ networks; rather, it is a compact, formula-driven, minimal-switch decomposition for Euclidean-residue families whose complement incidence is proved symbolically. The proof separates four ingredients: component-label collapse, anchor cancellation, noncollision of lifted switch representatives, and connected complement incidence. No infinite-family theorem in this manuscript is proved by finite witnesses or by computational enumeration. The theorem scope is stated for the parameter ranges where an algebraic complement-incidence certificate is written down. Tables and CSV data are used only to verify and reproduce the formulas, never as proof of an infinite-family theorem.
Keywords: Eisenstein–Jacobi networks, edge-disjoint Hamiltonian cycles, Hamiltonian decomposition, Cayley graphs, local switches, Eisenstein integers, interconnection networks.
1
Introduction
Hamiltonian decompositions are useful in interconnection networks because a spanning cycle supplies a simple ring for broadcasting, all-to-all communication, token circulation, diagnostics, and fault-tolerant routing. A degree-six network can contain at most three edge-disjoint Hamiltonian cycles (EDHCs), so a decomposition into three EDHCs is optimal: it covers every edge exactly once. 1
Let
√ 1+i 3 α = a + bρ, ρ= , (1) 2 and let EJα be the quotient graph over Z[ρ]/(α) with connection set {±1, ±ρ, ±ρ2 }. The graph has N = N(α) = a2 + ab + b2 (2) vertices and 3N undirected edges. Write d = gcd(a, b). If d = 1, each unit direction is a Hamiltonian cycle. If d > 1, each unit direction is a 2-factor with d cycles of length r = N/d. The non-coprime case was solved previously by a rectangular representation with d rows and r = N/d columns [2]. That construction proves existence for general non-coprime EJ networks. The present paper does not re-claim that existence result. Instead, it studies a sharper constructional question: Can one replace the rectangular exchange schedules by a compact local switch formula in the natural EJ Cayley geometry, using the minimum possible number of intercomponent switches for the first two cycles? The answer developed here is based on a minimal-alignment skeleton. Let H, V, D denote the three natural direction factors. We build H1 from H by d − 1 local rhombus switches and H2 from V by d − 1 local rhombus switches. The third cycle is forced as E(H3 ) = E(EJα ) \ E(H1 ) ∪ E(H2 ) . (3) The challenge is not the local switch itself. The challenge is choosing the correct representatives of the reduced switches on the quotient seams. A representative error can make H1 and H2 Hamiltonian but overlapping, or can make them disjoint while the complement splits into several cycles. The main contributions are as follows. • It proves a minimal switch skeleton: d − 1 switches for H1 and d − 1 switches for H2 , with a lower bound showing that d − 1 is necessary to collapse d direction cycles into one cycle. • It introduces anchor lock, which removes the only unavoidable two-edge overlap between the first two cycles in general-ratio cases. • It replaces rectangular exchange locations by Euclidean-residue phase rules depending on v mod u and on the same seam offset L that controls rectangular wraparound. • It proves a general admissible-lift theorem: any phase lift satisfying anchor lock, noncollision, and connected complement incidence gives three EDHCs. • It gives closed algebraic theorems for the Euclidean-residue families whose complementincidence words are derived symbolically. Rows without a written incidence derivation are reported only as reproducibility audits, not as theorems. • It explicitly states that all infinite-family theorem-level claims are mathematical. Finite boundary inventories and audit tables are not used to prove the infinite-family theorems. 2
2
Relation to the Rectangular Construction
The topology of Gaussian and EJ networks was studied in quotient-ring form by Flahive and Bose [1]. The closest prior EDHC result for non-coprime EJ networks is due to Hussain, Bose, and Al-Dhelaan [2]. They arrange vertices as iρ2 + k,
0 ≤ i < d,
0 ≤ k < r = N/d,
(4)
and exchange selected horizontal, vertical, and diagonal edges. Their method is a valid general existence construction. The present paper differs in construction and proof method. It works directly in the Cayley lattice, uses local rhombus switches rather than rectangular exchange schedules, uses the minimum possible number of intercomponent switches for the first two factors, and obtains the third cycle as a complement. In the even rectangular construction, the diagonal exchange schedule ranges over the long coordinate j = 0, . . . , r/2 − 1 [2]. The local construction targets O(d) switch sites. Since a b 2 2 , , (5) r = d(u + uv + v ), (u, v) = d d this is a significant description-length reduction when the reduced ratio is not tiny.
Figure 1: Positioning. Prior work proves non-coprime EJ EDHC existence through rectangular exchange schedules. This paper develops a local formula-based switch framework in the natural EJ Cayley geometry, using local rhombus operations, anchor lock, and seam-phase corrections.
3
Table 1: Notation used throughout the paper. Lift phases are denoted (πi , κi ) to avoid collision with the Euclidean quotient.
3
Symbol
Meaning
α = a + bρ N = a2 + ab + b2 d = gcd(a, b) r = N/d (u, v) = (a/d, b/d) A, B L sred = (ξi , ηi ) i si = sred + d(πi , κi ) i q0 h = v mod u H, V, D
EJ generator number of vertices number of natural cycles per direction length of each natural direction cycle reduced coprime ratio, normalized by 0 < u ≤ v Bezout pair satisfying uA + vB = 1 rectangular seam offset d(uB + v(B − A)) mod r reduced switch seed lifted seed and lift phases Euclidean quotient in v = q0 u + h first Euclidean residue horizontal, vertical, diagonal direction factors
Direction Factors and Component Labels
Use the basis {1, τ } where τ = ρ − 1,
ρ = 1 + τ.
(6)
A vertex is written as (x, y) = x + yτ . The positive direction bases are H = (1, 0),
V = (0, 1),
D = (1, 1).
(7)
Figure 2: The three EJ direction factors in the {1, τ } coordinate system. Lemma 1 (Direction-component labels). Let d = gcd(a, b). The components of the natural direction factors are labeled by H : y (mod d), V : x (mod d), D : x − y (mod d). Each direction factor consists of d cycles, each of length r = N/d.
4
(8) (9) (10)
Proof. An H step changes x and preserves y; a V step changes y and preserves x; and a D step changes both coordinates equally and preserves x − y. The quotient relation generated by α = (a + b) + bτ identifies these invariants modulo d = gcd(a, b). Each direction factor has exactly N undirected edges and is 2-regular. Hence its d components have equal length N/d.
4
Local Switch Calculus
A switch is a two-edge exchange inside a unit rhombus. It preserves degree two in the modified direction factor. Definition 1 (Rhombus switches). At seed s = (x, y): • H ← V removes horizontal bases (x, y) and (x, y + 1) and adds vertical bases (x, y) and (x + 1, y). • H ← D removes horizontal bases (x, y) and (x + 1, y + 1) and adds diagonal bases (x, y) and (x + 1, y). • V ← D removes vertical bases (x, y) and (x + 1, y + 1) and adds diagonal bases (x, y) and (x, y + 1).
Figure 3: A local two-edge rhombus switch. The switch preserves degree two and changes the component-incidence graph by one splice. Lemma 2 (Component action). An H ← V seed at (x, y) joins horizontal labels y and y +1. An H ← D seed at (x, y) joins horizontal labels y and y + 1. A V ← D seed at (x, y) joins vertical labels x and x + 1. Proof. The two removed edges lie in the two component labels stated. The two inserted opposite edges reconnect the four loose endpoints crosswise. If the two labels are distinct, this merges the two components. Each of the four vertices loses one incident edge and gains one incident edge, so degree two is preserved. Lemma 3 (Switch lower bound). Starting from a direction factor with d cycles, any localswitch construction that produces one Hamiltonian cycle from that factor must use at least d − 1 intercomponent switches. 5
Proof. A switch can reduce the number of connected components of a 2-factor by at most one. Reducing d components to one component therefore requires at least d − 1 switches.
5
Minimal-Alignment Skeleton
The first cycle H1 is obtained from the horizontal factor by SH (d) = {(H ← V, (0, 0))} ∪ {(H ← D, (d − 1, q)) : q = d − 1, d − 2, . . . , 2}. (11) It has d − 1 switches. The second cycle H2 starts from the vertical factor and uses V ← D switches. The reduced seed set has d − 1 elements. For even d, SVred (d) = {(−1, −1), (1, 0), (2, 0), . . . , (d − 2, 0)}.
(12)
For odd d, SVred (d) = {(−1, −1), (1, 0), (2, 0), . . . , (d − 3, 0), (d − 2, −1)}. (13) The seed (−1, −1) is the boundary bridge. All interior seeds lie on the alignment line z = x − y = x modulo d, except for the final odd-d boundary correction.
Figure 4: Quotient-level minimal-alignment skeleton. The first two direction factors collapse their d direction cycles using d − 1 switches each. Lemma 4 (Minimal collapse of H1 ). The switch list (11) induces a spanning tree on the H-component labels. Hence the modified horizontal factor is a Hamiltonian cycle. Proof. The seed (0, 0) of type H ← V joins horizontal labels 0 and 1. The seeds (d − 1, q) of type H ← D join labels q and q + 1 for q = d − 1, d − 2, . . . , 2 modulo d. Thus the induced label edges form a path through all residues of Zd . By Lemma 2, each switch preserves degree two and merges two current components. Since there are d − 1 such merges, the final 2-factor is connected and therefore is a Hamiltonian cycle. Lemma 5 (Minimal collapse of H2 ). The reduced seed sets (12) and (13) induce a spanning tree on the V -component labels. Therefore, any noncolliding lift of those seeds gives a Hamiltonian cycle in the vertical factor. 6
Proof. A V ← D seed with first coordinate x joins vertical labels x and x + 1. For even d, the first-coordinate residues are d − 1, 1, 2, . . . , d − 2, giving label edges {d − 1, 0}, {1, 2}, {2, 3}, . . . , {d − 2, d − 1},
(14)
which form a path through all residues. The odd case is identical, except that the final seed (d − 2, −1) supplies the edge {d − 2, d − 1} while placing the complement endpoint on the required boundary side. A noncolliding lift realizes the same label merges on actual cycles, so the final 2-factor is connected and Hamiltonian.
6
Lift Phases, Anchor Lock, and Seam Offsets
= (ξi , ηi ) has infinitely many representatives Each reduced seed sred i si = (ξi , ηi ) + d(πi , κi ),
πi , κi ∈ Z.
(15)
The variables (πi , κi ) are the lift phases. They determine where the reduced switch is placed on the quotient seam.
6.1
Anchor Lock
The first H1 switch, H ← V at (0, 0), inserts the two vertical edges based at (0, 0) and (1, 0). A V ← D switch at seed s removes vertical bases s and s + (1, 1). Therefore the first two H2 seeds must cancel those two borrowed vertical edges. Definition 2 (Anchor lock). A lift of SVred (d) satisfies anchor lock if the two reduced seeds with residues (−1, −1) and (1, 0) are lifted to representatives that remove the vertical bases (0, 0) and (1, 0). The canonical anchor lock is (−1, −1) 7→ (−1, −1),
(1, 0) 7→ (1, 0).
(16)
Lemma 6 (Anchor disjointness). If the first two H2 switches satisfy anchor lock, then the two vertical edges inserted into H1 by the seed (0, 0) are not present in H2 . Proof. The H ← V switch at (0, 0) inserts the vertical bases (0, 0) and (1, 0). The V ← D switch at (−1, −1) removes vertical bases (−1, −1) and (0, 0). The V ← D switch at (1, 0) removes vertical bases (1, 0) and (2, 1). Hence both borrowed anchor edges are deleted from the vertical factor before H2 is finalized.
7
Figure 5: Anchor-lock mechanism. Before the lock, the first H1 switch borrows two vertical edges from the vertical factor and creates a local edge conflict. The two anchor-lock seeds delete those borrowed vertical bases from the construction of H2 , restoring edge-disjointness without changing the component-collapse skeleton.
6.2
The Rectangular Offset and the First Euclidean Residue
Let a = du,
b = dv,
gcd(u, v) = 1,
(17)
where 0 < u ≤ v after applying the usual EJ symmetry normalization. Let r=
N = d(u2 + uv + v 2 ). d
Choose integers A, B such that
(18) (19)
uA + vB = 1. The rectangular wrap offset is L ≡ d uB + v(B − A)
(mod r).
(20)
This offset identifies the seam shift of the quotient rectangle. It depends on both u and v, not only on d or v. The residue h≡v
(mod u),
0 < h < u (u > 1)
(21)
is the first Euclidean step of the reduced ratio. Remark 1 (Motivating example: why L alone is not enough). The normalized offset L/d is an essential seam coordinate, but it is not by itself a complete phase invariant. For example, the multiplier ratio (1, 4) and the general ratio (2, 5) have the same normalized offset value, yet their verified symbolic phase rules use opposite κ-correction signs. The first Euclidean residue v mod u distinguishes the two cases. Thus the phase rule must use the seam offset together with the Euclidean residue branch; this remark is a scope warning, not an additional theorem. 8
7
Admissible Lifts and the Main Switch Theorem
The following definition isolates the exact conditions needed for the local formula to be a complete EDHC decomposition. Definition 3 (Admissible lift). A lift Φ = {(πi , κi )} of SVred (d) is called admissible if the following four conditions hold. (A1) Anchor lock: the lift satisfies Definition 2. (A2) No repeated switch bases: the lifted V ← D switches remove distinct vertical bases and add distinct diagonal bases. (A3) No H1 /H2 collision: after anchor cancellation, no edge inserted in H1 is also present in H2 . (A4) Connected complement incidence: after removing the diagonal bases used by H1 and H2 , the released horizontal and vertical bases induce a connected incidence graph on the diagonal arc labels z = x − y (mod d). Theorem 1 (Admissible-lift EDHC theorem). Let d > 1. Construct H1 by (11). Construct H2 from SVred (d) using an admissible lift. Let H3 be the complement (3). Then H1 , H2 , H3 are three pairwise edge-disjoint Hamiltonian cycles of EJα . Proof. By Lemma 4, H1 is a connected spanning 2-factor and hence a Hamiltonian cycle. By Lemma 5 and conditions (A1)–(A2), H2 is also a connected spanning 2-factor. Condition (A3), together with Lemma 6, gives E(H1 ) ∩ E(H2 ) = ∅. Since EJα is 6-regular and H1 , H2 are disjoint 2-factors, the complement H3 is a spanning 2-factor. The diagonal parts of H3 are path arcs obtained by deleting the diagonal bases used by H1 and H2 ; the horizontal and vertical edges released by the switches connect endpoints of those arcs. By condition (A4), the arc-incidence graph is connected, so all arcs lie in one connected component of H3 . Therefore H3 is a connected spanning 2-factor, which is a Hamiltonian cycle. Pairwise edge-disjointness follows from the definition of H3 as the unused edge set. The rest of the paper gives explicit phase maps and proves or audits their admissibility. This separates the graph-theoretic theorem from the arithmetic problem of selecting seam representatives.
8
Phase Operators
It is useful to state phase rules with compact operators. The first two anchor seeds are fixed by (16). For all other seeds, write xi ∈ {2, 3, . . . , d − 2} for the reduced alignment label.
9
Definition 4 (Phase operators). For a non-anchor seed with alignment label ξi , define: QE (c) : QE,h (c) : QO,h (c) : Poddtail (−1) : Palltail (−1) :
κi ← κi + c for even ξi , 2 ≤ ξi ≤ d − 2, κi ← κi + c for even ξi , 4 ≤ ξi ≤ ⌊d/2⌋, κi ← κi + c for odd ξi , 3 ≤ ξi ≤ ⌊d/2⌋, πi ← πi − 1 for odd ξi > d/2, πi ← πi − 1 for ξi > d/2.
(22) (23) (24) (25) (26)
These are not exchange tables. They are arithmetic phase corrections applied to the fixed reduced switch skeleton.
9
Euclidean-Residue Phase Theorems
This section contains only mathematical statements. Tables in the paper and in the supplemental archive summarize or verify formulas; they are not used as proof. The theorem-level families below are proved by substituting their phase operators into connector-label identities and by proving that the resulting complement-incidence graph is the path determined by the alternating word Wd = (0, d − 1, 1, d − 2, 2, d − 3, . . .).
(27)
Equivalently, for every index for which the terms are defined, w2s = s,
w2s+1 = d − 1 − s.
(28)
Definition 5 (Complement-incidence certificate). For a lifted seed set, delete from the natural diagonal factor all diagonal bases used by H1 and H2 . The remaining diagonal pieces are arcs labeled by z = x − y (mod d). A complement-incidence certificate is an algebraic identity proving that the released horizontal and vertical connector bases realize exactly Cj = {wj , wj+1 },
j = 0, . . . , d − 2,
(29)
for the word Wd in (27). Since Wd is a permutation of Zd , the pairs in (29) form a path on all d diagonal labels. In particular, no proper subset of labels closes into a component. Lemma 7 (Connector-label identities). Let z(x, y) = x−y (mod d) be the diagonal-component label of a vertex. A horizontal connector released to the complement from base (x, y) joins diagonal arc labels z(x, y) and z(x, y) + 1, (30) whereas a vertical connector released from base (x, y) joins diagonal arc labels z(x, y)
and
z(x, y) − 1.
(31)
Moreover, replacing a seed (x, y) by a lift (x, y) + d(π, κ) does not change the label z(x, y) (mod d). 10
Proof. A horizontal edge sends (x, y) to (x + 1, y), so x − y increases by one. A vertical edge sends (x, y) to (x, y + 1), so x − y decreases by one. Diagonal edges preserve x − y. Finally, a lift by d(π, κ) changes x − y by d(π − κ), which is zero modulo d. For example, when d = 8, a released horizontal base whose lower endpoint has diagonal label 3 has endpoint labels 3 and 4, giving the concrete terminal connector 3 → 4 in W8 = (0, 7, 1, 6, 2, 5, 3, 4). Lemma 8 (Reduced connector word). For the minimal reduced skeleton (11), (12), and (13), after anchor lock the released connector labels are exactly the pairs {w0 , w1 }, {w1 , w2 }, . . . , {wd−2 , wd−1 },
(32)
where Wd is defined by (28). Proof. The anchor-locked seeds remove the two vertical bases inserted into H1 and release the first connector {0, d − 1} = {w0 , w1 }. For s ≥ 0, the reduced alignment seed with label s + 1 releases, by Lemma 7, a connector from d − 1 − s to s + 1; this is {w2s+1 , w2s+2 }. The matching horizontal release from the H1 side gives the connector from s + 1 to d − 2 − s, namely {w2s+2 , w2s+3 }. First suppose d = 2t is even. Then Wd = (0, 2t − 1, 1, 2t − 2, . . . , t − 1, t). The indices s = 0, 1, . . . , t − 2 produce the 2t − 2 connectors {w1 , w2 }, {w2 , w3 }, . . . , {w2t−2 , w2t−1 }.
(33)
Together with the anchor connector {w0 , w1 }, these are all d − 1 = 2t − 1 consecutive pairs of Wd . There is no repetition because the reduced seed labels used in (12) are distinct modulo d and the displayed pairs have distinct positions in the word. Now suppose d = 2t + 1 is odd. The same argument with s = 0, 1, . . . , t − 2 produces all consecutive pairs up to {w2t−2 , w2t−1 } = {t − 1, t + 1}. The only missing terminal pair is {w2t−1 , w2t } = {t + 1, t}.
(34)
The final reduced seed (d − 2, −1) has diagonal label (d − 2) − (−1) ≡ d − 1
(mod d),
(35)
and the boundary-side endpoint of this seed supplies exactly this terminal pair, rather than duplicating any earlier pair. To make the odd case explicit, take d = 7 so t = 3 and W7 = (0, 6, 1, 5, 2, 4, 3).
(36)
The anchor gives {0, 6}. The ordinary indices s = 0, 1 give the four pairs {6, 1}, {1, 5}, {5, 2}, {2, 4}.
(37)
The remaining terminal pair is {4, 3} = {w5 , w6 }. The odd boundary seed is (5, −1), whose diagonal label is z(5, −1) = 5−(−1) ≡ 6 (mod 7); because it is placed on the boundary side, its released connector endpoint is the terminal unused label 3 rather than an earlier prefix label. Thus it supplies {4, 3} and completes the path 0 − 6 − 1 − 5 − 2 − 4 − 3. The general d = 2t + 1 case is identical: the ordinary indices stop at {t − 1, t + 1}, and the boundary seed supplies the unique remaining terminal pair {t + 1, t}. Hence all d − 1 consecutive pairs in (32) are produced without gap or repeat. 11
Figure 6: Connector-label worked example for d = 6. The released connectors realize consecutive pairs in the alternating word W6 = (0, 5, 1, 4, 2, 3), so the complement-incidence graph is a path rather than a closed subcycle.
Figure 7: Early closure and seam-phase correction. The reduced connector tree is unchanged, but a wrong lift can close a proper subset of diagonal arcs. The phase correction QE shifts the seam band and realizes the full Hamiltonian path in the complement-incidence graph. Lemma 9 (Phase-band noncollision). For each of the four phase families in Theorem 2, the stated P - and Q-operators satisfy admissibility conditions (A1)–(A3): anchor lock, distinct removed bases, distinct inserted diagonal bases, and pairwise edge-disjointness of H1 and H2 . Proof. Condition (A1) is the anchor-lock equation (16). We prove (A2) and (A3) by recording, for every non-anchor lifted seed, bi = (ξi , ηi ; πi , κi ). Two switch bases can coincide only if both their reduced seed coordinate (ξi , ηi ) and their lift band (πi , κi ) agree. The reduced labels ξi of the non-anchor seeds are distinct, so no two ordinary seeds collide before quotient wrapping is considered. The only remaining risk is a 12
seam collision between a tail seed and its reflected boundary mate. The P -operators change the longitudinal band πi , and the Q-operators change the transverse band κi ; hence a tail or parity-band seed that could meet a boundary mate is moved to a different band. Explicitly, after the anchor seeds are fixed, the band arithmetic in the four theorem-level families is as follows: (1, m) :
πi = 0,
(2, 3) :
πi = −1{ξi >d/2} ,
(2, v), v ≥ 5 odd : (t, t + 1), t ≥ 5 :
κi = 1{ξi even, 4≤ξi ≤⌊d/2⌋} , κi = 21{ξi even, 4≤ξi ≤⌊d/2⌋} ,
πi = −1{ξi odd, ξi >d/2} , πi = 0,
κi = −1{ξi even} ,
κi = −31{ξi even} .
In each line, two seeds with different reduced labels keep different first components of bi , while any seed in a possible seam-contact class has a nonzero πi or κi different from the corresponding boundary mate. Therefore the removed vertical bases and inserted diagonal bases are distinct, proving (A2). For (A3), Lemma 6 removes the two vertical anchor edges shared before anchor lock. The non-anchor diagonal bases inserted by H1 lie on the unshifted seam band determined by (11). The displayed four band formulas show that every non-anchor H2 diagonal insertion that could otherwise meet this seam is shifted by κ = +1, κ = +2, κ = −1, or κ = −3, or by the longitudinal move π = −1 on the tail. Thus the H1 and H2 diagonal insertion bands are disjoint. Combining this with the anchor cancellation gives E(H1 ) ∩ E(H2 ) = ∅ for the first two constructed factors, which is (A3). Theorem 2 (Euclidean-residue phase theorem). Assume 0 < u ≤ v, gcd(u, v) = 1, and d ≥ 4. The minimal-alignment construction gives three EDHCs for each of the following phase families: 1. (u, v) = (1, m), m ≥ 5, with phase rule QE,h (+1); 2. (u, v) = (2, 3) with phase rule Palltail (−1) + QE,h (+2); 3. (u, v) = (2, v), odd v ≥ 5, with even d ≥ 4 and phase rule Poddtail (−1) + QE (−1); 4. (u, v) = (t, t + 1), t ≥ 5, with phase rule QE (−3). Proof. By Lemma 9, the four listed phase families satisfy (A1)–(A3). By Lemma 8, the connector labels are the consecutive pairs of the permutation word Wd . The lift phases in the four families do not alter connector labels modulo d by Lemma 7; they only choose seam representatives that avoid the collisions excluded in Lemma 9. Hence the complementincidence graph is the path w0 − w1 − · · · − wd−1 . It is connected and has no proper closed prefix, so (A4) holds. The admissible-lift theorem, Theorem 1, now gives three pairwise edge-disjoint Hamiltonian cycles.
13
(a) H1
(b) H2
(c) H3
Cycle
|E|
internal
wrap
H-dir
V-dir
D-dir
H1 H2 H3
48 48 48
36 37 40
12 11 8
42 0 6
2 42 4
4 6 38
total
144
113
31
–
–
–
Figure 8: Illustrative EDHC decomposition for α = 4 + 4ρ, N = 48, and d = 4. Panels (a)–(c) show the three Hamiltonian cycles H1 , H2 , H3 . Solid edges are internal edges and dashed edges are wraparound quotient edges. The compact table reports edge counts and direction counts for this example only; the theorem is proved algebraically, not by this figure. Example 1 (Full lift-phase computation for a non-multiplier family). Consider the first non-multiplier family (u, v) = (2, 5) with d = 6. Then ρ-generator: α = 2 · 6 + 5 · 6ρ = 12 + 30ρ, N = 122 + 12 · 30 + 302 = 1404, r = N/d = 234.
(38)
Since the construction itself uses the τ = ρ − 1 basis, the same generator is α = 12 + 30ρ = 12 + 30(1 + τ ) = 42 + 30τ,
(39)
so the seed coordinates below are interpreted in the {1, τ } coordinate system used throughout Sections III–IX. The even-d reduced skeleton is SVred (6) = {(−1, −1), (1, 0), (2, 0), (3, 0), (4, 0)}.
(40)
Write each lift as si = (ξi , ηi ) + 6(πi , κi ). The anchor-lock seeds are (−1, −1) and (1, 0), so their phases remain (0, 0). For this family Theorem 2 uses Poddtail (−1) + QE (−1). 14
(41)
Here d/2 = 3. The operator Poddtail (−1) applies only to odd labels ξi > 3; the only tail label is ξ = 4, which is even, so no Poddtail shift occurs. The operator QE (−1) applies to the even labels ξ = 2 and ξ = 4. Therefore the phase vector is (ξi , ηi ) (−1, −1) (1, 0) (2, 0) (3, 0) (4, 0) (πi , κi ) (0, 0) (0, 0) (0, −1) (0, 0) (0, −1)
(42)
and the final lifted seeds are (−1, −1),
(1, 0),
(2, −6),
(3, 0),
(4, −6).
(43)
The reduced first coordinates are distinct, so the removed vertical bases are distinct (A2). The two anchor seeds delete the two vertical bases borrowed by H1 (A1 and A3). The two even-band shifts place the non-anchor diagonal insertions on a different transverse seam, so no diagonal base used by H1 is reused by H2 . Example 2 (Explicit finite boundary certificates for d = 2 and d = 3). The theorem-level families are stated for d ≥ 4, but the two smallest non-coprime values can be closed by explicit finite switch inventories. These finite inventories are boundary certificates only; they are not used to prove Theorem 2. For d = 2, take α = 2+2ρ, so N = 22 +2·2+22 = 12. Use one H1 switch (H ← V, (0, 0)) and the H2 certificate of V ← D switches (1, 0),
(0, 1),
(−1, −1).
(44)
In the half-open Pα representatives, the resulting first two Hamiltonian cycles have edge inventories E(H1 ) = {((0, 0), (1, 2)), ((0, 0), (1, 3)), ((0, 1), (1, 1)), ((−1, 2), (0, 2)), ((−1, 2), (0, 4)), ((0, 2), (1, 2)), ((−1, 3), (0, 3)), ((−1, 3), (0, 5)), ((0, 3), (1, 3)), ((−1, 4), (0, 1)), ((−1, 4), (0, 4)), ((0, 5), (1, 1))}, E(H2 ) = {((0, 0), (0, 5)), ((0, 1), (0, 2)), ((−1, 2), (0, 1)), ((−1, 2), (1, 3)), ((1, 2), (1, 3)), ((−1, 3), (0, 0)), ((−1, 3), (0, 2)), ((0, 3), (1, 2)), ((−1, 4), (1, 1)), ((−1, 4), (0, 3)), ((0, 4), (1, 1)), ((0, 4), (0, 5))}.
Direct comparison gives |E(H1 )| = |E(H2 )| = 12 and E(H1 ) ∩ E(H2 ) = ∅; the unused complement has 12 edges and is a connected 2-factor, so it is H3 . For d = 3, take α = 3 + 3ρ, so N = 27. Use (11) for H1 and the H2 certificate (0, 0),
(1, 0),
(0, −2),
(2, 0).
(45)
Substituting these four V ← D seeds into the switch inventory gives |E(H1 )| = |E(H2 )| = |E(H3 )| = 27, zero pairwise intersections, degree two at every vertex, and one component in each factor. Thus the d = 3 boundary case is also closed explicitly. Remark 2 (Why no finite witnesses are used). Theorem 2 is a symbolic statement for d ≥ 4. It does not depend on enumerating any finite quotient and it does not use the audit tables as proof. The boundary values d = 2, 3 are handled above by explicit finite edge inventories; they are included only to close the small cases and are not hidden base cases for the infinitefamily proof. Additional residue rows are likewise reported only as audits unless a symbolic connector-word proof is written down. 15
Table 2: Formula summary for the theorem-level phase families. This table is a reader aid only; the proof is given by Lemmas 7–9 and Theorem 2.
10
Reduced ratio family
Condition
Phase correction
theorem scope
(1, m) (2, 3) (2, v) (t, t + 1)
m≥5 QE,h (+1) d≥4 special first residue Palltail (−1) + QE,h (+2) d ≥ 4 odd v ≥ 5 Poddtail (−1) + QE (−1) even d ≥ 4 t≥5 QE (−3) d≥4
Consequences and Theorem Scope
The following corollaries are immediate restatements of Theorem 2; they do not introduce additional assumptions and do not rely on validation data. Corollary 1 (Multiplier family). For every d ≥ 4 and every m ≥ 5, the generator α = d + mdρ has three EDHCs under the minimal-alignment construction. Proof. Apply Theorem 2 with (u, v) = (1, m). Corollary 2 (Odd (2, v) family). For every even d ≥ 4 and every odd v ≥ 5, the generator α = 2d + vdρ has three EDHCs under the minimal-alignment construction. Proof. Apply Theorem 2 with (u, v) = (2, v). The even-d restriction is part of the algebraic theorem scope because the odd-tail P -operator interacts with the boundary bridge seed differently when d is odd; a separate odd-d word is not claimed here. Corollary 3 (Consecutive ratios). For every d ≥ 4 and every t ≥ 5, the generator α = dt + d(t + 1)ρ has three EDHCs under the minimal-alignment construction. Proof. Apply Theorem 2 with (u, v) = (t, t + 1). Additional rows observed for u = 3, 4, 5 are not theorem statements in this version. They appear only in the deterministic audit because their connector order involves cross-parity interactions after the first Euclidean residue step. Closing those rows algebraically appears to require a second Euclidean-residue split and a separate permutation word, rather than the single word Wd used above.
11
Universal Euclidean Program: Discussion Only
The certified theorem scope above is intentionally narrower than the full all-ratio problem. The data and endpoint inventories suggest that an eventual universal theorem should be recursive in the Euclidean algorithm v = q0 u + h0 ,
0 < h0 < u,
(46)
but this paper does not state that recursive theorem as proved. The reason is structural: the graph-theoretic part is solved by Theorem 1; the remaining work is an arithmetic 16
seam theorem proving that the selected Euclidean residue bands always realize a connected complement-incidence word and never close early. Thus the universal statement is kept as a research program, not as a proposition. Completing it would require a closed formula for all residue classes and a symbolic certificate analogous to the connector-word certificate in Lemma 8 for every Euclidean branch.
12
Algorithm and Complexity
Algorithm 1 summarizes the construction for the certified residue catalog. It contains no search over seed subsets. The phase rule is selected from Table 2. Algorithm 1 Minimal-alignment EJ EDHC construction Require: a, b, α = a + bρ, N = a2 + ab + b2 , d = gcd(a, b) 1: if d = 1 then 2: return the three natural unit-direction Hamiltonian cycles 3: end if 4: normalize the reduced ratio (u, v) = (a/d, b/d) so 0 < u ≤ v 5: build H1 from H using (11) 6: build the reduced H2 seed list using (12) or (13) 7: compute L from (20) and the first residue v mod u 8: apply anchor lock to the first two H2 seeds 9: apply a certified phase correction from Table 2 10: construct H2 from V using the lifted V ← D switches 11: set H3 = E(EJα ) \ (E(H1 ) ∪ E(H2 )) 12: return H1 , H2 , H3 The construction uses 2(d − 1) switches. Once the switch list is known, listing the three cycles takes O(N ) time. The switch description itself has length O(d), while the even rectangular diagonal schedule has length Θ(r) = Θ(N/d).
13
Deterministic Audit and Reproducibility
The validation program is an audit of the formulas, not a substitute for proof. All infinitefamily theorem-level claims above are proved mathematically before any audit is mentioned; tables and CSV logs in this section are for verification and reproducibility only. For each case it checks |E(H1 )| = |E(H2 )| = |E(H3 )| = N, (47) degree two at every vertex, connectedness of all three factors, zero pairwise intersections, E(Hi ) ∩ E(Hj ) = ∅ (i ̸= j),
(48)
and full union size 3N . The implementation records all lifted seeds, all edge counts, all pairwise intersections, and the connected-component count of each factor. 17
Table 3: Deterministic audit summary. These data are verification only and are not used as proof. Ratios audited
d values
Result
(1, 3), (1, 5), (1, 6), (1, 7) (2, 3), (2, 5), (2, 7) (3, 4), (3, 5), (3, 7) (4, 5), (4, 7) u = 5, 6, 7 families Consecutive u = 8, . . . , 12
40, 50, 60 4–20, 40 4–20, 40 4–20, 40 8, 10, 12, 14, 16, 20 8, 10, 12
all pass all pass all pass all pass all pass all pass
For the consecutive high-u audit, the displayed ceiling is lower than some other rows because the vertex count grows as N = d2 (u2 + u(u + 1) + (u + 1)2 ); the consecutive family itself is theorem-level through the symbolic certificate, so this ceiling is a runtime audit choice rather than a mathematical boundary. The audit also illustrates two structural facts already handled in the proof. Before anchor lock, general-ratio candidates can have exactly two shared edges between H1 and H2 ; those are the two vertical anchor edges. After anchor lock, remaining failures are complementconnectivity failures caused by early closure of diagonal arcs. The residue phase correction prevents this early closure in the certified rows.
14
Discussion
The paper should be read as a formulaic improvement over the rectangular existence construction, not as the first existence proof. Its contribution is the minimal local skeleton, the anchor-lock invariant, and the Euclidean-residue phase mechanism. Theorem 1 gives a clean graph-theoretic endpoint: once a lift is admissible, the EDHC property follows immediately. Theorem 2 gives a certified catalog and promotes only the rows with written incidence certificates to infinite-family corollaries. This prevents the common error of using an audit table as a proof. The current version is therefore stronger than a table-driven or purely computational draft, but it remains honest about scope. The all-ratio theorem requires completing the recursive Euclidean phase map. This is now a precise arithmetic problem about seam bands, not an open-ended graph-search problem.
15
Conclusion
This paper presented a certified Euclidean-residue minimal-alignment switch framework for three edge-disjoint Hamiltonian cycles in Eisenstein–Jacobi networks. The construction uses the minimum possible d − 1 switches to collapse the first direction factor and the minimum possible d − 1 switches to collapse the second direction factor. The third cycle is obtained as the edge complement. The proof is based on component labels, local degree preservation, anchor cancellation, residue phases, edge inventories, and complement incidence rather than exchange tables.
18
The paper closes a substantial theorem scope: multiplier families, the odd (2, v) family in its even-d parity range, and the consecutive family (t, t + 1) for t ≥ 5. The all-ratio Euclidean program remains a natural extension, but the results proved here already provide a compact, minimal-switch, formula-driven alternative to rectangular exchange schedules for certified classes of non-coprime EJ networks.
Acknowledgment The author gratefully acknowledges Kuwait University and the Department of Computer Science, Faculty of Science, Kuwait University, for their support and for providing the academic environment and institutional encouragement that made this research possible.
References [1] M. Flahive and B. Bose, “The topology of Gaussian and Eisenstein–Jacobi interconnection networks,” IEEE Transactions on Parallel and Distributed Systems, vol. 21, no. 8, pp. 1132–1142, 2010. [2] Z. A. Hussain, B. Bose, and A. Al-Dhelaan, “Edge disjoint Hamiltonian cycles in Eisenstein–Jacobi networks,” Journal of Parallel and Distributed Computing, vol. 86, pp. 62–70, 2015. [3] C. Martinez, E. Stafford, R. Beivide, and E. M. Gabidulin, “Modeling hexagonal constellations with Eisenstein–Jacobi graphs,” Problems of Information Transmission, vol. 44, no. 1, pp. 1–11, 2008. [4] B. Albader and B. Bose, “Edge disjoint Hamiltonian cycles in Gaussian networks,” IEEE Transactions on Computers, vol. 65, no. 1, pp. 315–321, 2016. [5] C. Martinez, R. Beivide, E. Stafford, M. Moreto, and E. M. Gabidulin, “Modeling toroidal networks with the Gaussian integers,” IEEE Transactions on Computers, vol. 57, no. 8, pp. 1046–1056, 2008. [6] M. M. Bae and B. Bose, “Edge-disjoint Hamiltonian cycles in k-ary n-cubes and hypercubes,” IEEE Transactions on Computers, vol. 52, no. 10, pp. 1271–1284, 2003. [7] M. Bae and B. Bose, “Gray codes for torus and edge disjoint Hamiltonian cycles,” in Proc. 14th International Parallel and Distributed Processing Symposium, 2000, pp. 365– 370. [8] M. Bae, B. Bose, and B. F. AlBdaiwi, “Edge-disjoint Hamiltonian cycles in twodimensional torus,” International Journal of Mathematics and Mathematical Sciences, vol. 2004, no. 25, pp. 1299–1308, 2004. [9] S. Latifi and S.-Q. Zheng, “On link-disjoint Hamiltonian cycles of torus networks,” in Proc. IEEE Southeastcon, 1993. 19
[10] P. Jha and R. Prasad, “Hamiltonian decomposition of the rectangular twisted torus,” IEEE Transactions on Parallel and Distributed Systems, vol. 23, no. 8, pp. 1504–1507, 2012. [11] R. Rowley and B. Bose, “Edge-disjoint Hamiltonian cycles in De Bruijn networks,” in Proc. Sixth Distributed Memory Computing Conference, 1991, pp. 707–709. [12] R. Rowley and B. Bose, “On the number of arc-disjoint Hamiltonian circuits in the De Bruijn graphs,” Parallel Processing Letters, vol. 3, no. 4, pp. 375–382, 1993. [13] M. Anantha, R. Prasad, and B. F. AlBdaiwi, “Mixed-radix Gray codes in Lee metric,” IEEE Transactions on Computers, vol. 56, no. 10, pp. 1297–1307, 2007. [14] C. C. Chen and N. F. Quimpo, “On strongly Hamiltonian abelian group graphs,” in Combinatorial Mathematics VIII, Lecture Notes in Mathematics, vol. 884. Springer, 1981, pp. 23–34. [15] D. Witte and J. A. Gallian, “A survey: Hamiltonian cycles in Cayley graphs,” Discrete Mathematics, vol. 51, no. 3, pp. 293–304, 1984. [16] J.-C. Bermond, O. Favaron, and M. Maheo, “Hamiltonian decomposition of Cayley graphs of degree 4,” Journal of Combinatorial Theory, Series B, vol. 46, pp. 142–153, 1989. [17] B. Alspach, “The wonderful Walecki construction,” Bulletin of the Institute of Combinatorics and its Applications, vol. 52, pp. 7–20, 2008. [18] J. Duato, S. Yalamanchili, and L. Ni, Interconnection Networks: An Engineering Approach. Morgan Kaufmann, 2003. [19] A. Grama, A. Gupta, G. Karypis, and V. Kumar, Introduction to Parallel Computing, 2nd ed. Addison-Wesley, 2003. [20] G. H. Hardy and E. M. Wright, An Introduction to the Theory of Numbers, 5th ed. Oxford University Press, 1980. [21] N. Biggs, Algebraic Graph Theory, 2nd ed. Cambridge University Press, 1993. [22] C. Godsil and G. Royle, Algebraic Graph Theory. Springer, 2001. [23] J. A. Bondy and U. S. R. Murty, Graph Theory. Springer, 2008.
20