A Unified Constant-Time Switch Rule for Constructing Edge-Disjoint Hamiltonian Cycles in Gaussian Networks Bader Albader
arXiv:2606.16892v1 [cs.DC] 15 Jun 2026
Department of Computer Science, Faculty of Science, Kuwait University, Safat 13060, Kuwait [email protected]
Abstract Gaussian networks are degree-four symmetric interconnection networks defined over residue classes of Gaussian integers. Earlier work showed that when the generator α = a + bi satisfies gcd(a, b) = 1, the real and imaginary dimensions directly form two edge-disjoint Hamiltonian cycles. A later construction extended the result to the non-coprime case gcd(a, b) = d > 1, but its proof used long node-sequence tables and separate odd/even cases for d. This paper gives a unified closed-form construction that covers both d = 1 and d > 1, and also covers both odd and even d, without separate case tables. In the rectangular representation with d rows and r = (a2 +b2 )/d columns, the construction uses a constant-time local switch rule for each q = 1, 2, . . . , d − 1 at column aq = q − 1. Each switch removes two horizontal edges and inserts two vertical edges. The switched horizontal structure forms the first Hamiltonian cycle, while its edge-complement in the Gaussian network forms the second Hamiltonian cycle. Thus, the full edge set is partitioned into two edge-disjoint Hamiltonian cycles. The construction requires O(d) switch-generation time and O(N ) time to list the two cycles, where N = a2 + b2 . Exhaustive validation for all 1 ≤ a ≤ b ≤ 100, excluding only the degenerate N = 2 network, and large-scale validation up to N = 3,250,000 confirm the construction.
Keywords: Edge-disjoint Hamiltonian cycles; Gaussian networks; Gaussian integers; interconnection networks; Hamiltonian cycle; parallel processing; successor rule; algebraic networks MSC 2020: 05C45; 05C38; 05C85; 68M10
1
Introduction
Gaussian networks are algebraic interconnection networks defined over quotient rings of Gaussian integers. They are regular degree-four networks whose vertices are residue classes modulo a Gaussian integer α = a + bi, and whose links correspond to adding or subtracting the Gaussian units 1 and i [1, 2]. Because they are algebraically regular and symmetric, 1
Gaussian networks are useful for modeling toroidal-like interconnection networks with compact routing and wrap-around structure. Hamiltonian cycles are important in interconnection networks because a Hamiltonian cycle embeds a spanning ring through all processors. Such rings are useful for broadcasting, all-to-all communication, and load-balanced message circulation. Multiple edge-disjoint Hamiltonian cycles (EDHCs) are even more useful because they provide independent spanning rings, allowing communication traffic to be distributed and improving tolerance to edge faults [4, 5, 6, 8, 9, 11]. Recent work continues to use EDHCs as a structural tool for fault-tolerant broadcasting and data-center/interconnection-network design [9, 11, 12]. For Gaussian networks, the EDHC problem naturally splits according to d = gcd(a, b).
(1)
When d = 1, the real dimension alone forms a Hamiltonian cycle and the imaginary dimension alone forms another Hamiltonian cycle. This gives two edge-disjoint Hamiltonian cycles immediately [2]. When d > 1, however, the real-dimension edges decompose into d disjoint cycles, and the imaginary-dimension edges also decompose into d disjoint cycles. The non-coprime case therefore requires a splicing mechanism to join these smaller cycles. The non-coprime case was previously solved by Albader and Bose using explicit node-sequence tables for odd and even d [3]. The present paper is written to be self-contained: all definitions, switch rules, correctness proofs, and algorithms needed for the unified construction are included here. The earlier construction established existence but was relatively long and difficult to implement directly. This paper provides a simpler and unified solution. It shows that one closed-form switching rule handles all cases: q = 1, 2, . . . , d − 1,
aq = q − 1.
(2)
For d = 1, there are no switches and the construction reduces exactly to the classical coprime case. For d > 1, the same formula splices the d horizontal cycles into one Hamiltonian cycle and simultaneously splices the complementary vertical cycles into the second Hamiltonian cycle. Thus, the new construction unifies the earlier d = 1 result and the later d > 1 result in one algorithmic framework. From a graph-theoretic perspective, the result gives an explicit decomposition of the full edge set of every nondegenerate Gaussian network into two Hamiltonian 2-factors. The main contributions are: • a unified EDHC construction for nondegenerate Gaussian networks that covers d = 1, d > 1, odd d, and even d; • a closed-form constant-time switch rule aq = q − 1, replacing the previous odd/even case tables; • complete algorithms for constructing the switch set and traversing the two Hamiltonian cycles; • a proof that the switched graph is one Hamiltonian cycle, that its edge-complement is also one Hamiltonian cycle, and that the two cycles are edge-disjoint; 2
• exhaustive validation for all 1 ≤ a ≤ b ≤ 100 and large-scale validation up to 3,250,000 vertices.
2
Related Work and Positioning
Gaussian networks were introduced and studied as algebraic models of toroidal networks in [1]. The topology of Gaussian and Eisenstein–Jacobi interconnection networks was further developed in [2], including distance, routing, and Hamiltonian-cycle properties. In particular, when gcd(a, b) = 1, the two natural dimensions of Ga+bi give two EDHCs. The non-coprime Gaussian case was later addressed by Albader and Bose [3]. In that case, the +1 edges form d = gcd(a, b) disjoint cycles and the +i edges form another d disjoint cycles. The earlier non-coprime construction spliced those cycles but required separate odd/even cases and long tables of node sequences. The present paper differs from both earlier steps. It does not only cover d = 1, and it does not only cover d > 1. Instead, it gives a single algorithm that covers both. Table 1 summarizes the difference. Table 1: Positioning of the present construction. Work Flahive and Bose [2] Albader and Bose [3] This paper
Case covered d=1 d>1 d = 1 and d > 1
Construction style Direct dimension cycles Odd/even sequence tables Unified closed-form switch rule
Outside Gaussian networks, EDHCs have been studied in several interconnection topologies, including hypercubes and k-ary n-cubes [4], butterfly graphs [5], twisted and locally twisted cubes [6, 7], augmented cubes [8], folded locally twisted cubes and folded crossed cubes [9], balanced hypercubes [10], and BCube data-center networks [11]. Recent graphtheoretic work has also studied EDHCs in symmetric and Cayley-type graphs [12]. These works show that EDHC constructions remain active and relevant for both network theory and communication applications.
3
Preliminaries
Let Z[i] = {x + yi : x, y ∈ Z}
(3)
be the ring of Gaussian integers. The norm of α = a + bi is N (α) = a2 + b2 .
(4)
Definition 1. (Gaussian network) Let α = a + bi ̸= 0. The Gaussian network generated by α is the graph Gα = (V, E), (5) where V = Z[i]/(α), 3
(6)
and two vertices β, γ ∈ V are adjacent if and only if β − γ ≡ ±1
±i
or
(mod α).
(7)
The number of vertices is |V | = N = a2 + b2 .
(8)
Throughout the paper, assume 0 < a ≤ b. Let d = gcd(a, b),
3.1
r=
a2 + b 2 . d
(9)
Rectangle Representation
The rectangle representation uses the complete residue system S = {(x, y) : 0 ≤ x < r, 0 ≤ y < d}.
(10)
Thus, each vertex is represented by a pair (x, y), with x taken modulo r and y restricted to 0, . . . , d − 1. Let u, v ∈ Z satisfy ua + vb = d. (11) Define n ≡ av − bu
(mod r).
(12)
Then the rectangle representation has the wrap relation −i ≡ n + (d − 1)i
(mod α).
(13)
Consequently, di ≡ −n
(mod α).
(14)
The moves in rectangle coordinates are: E(x, y) = (x + 1 mod r, y), W (x, y) = (x − 1 mod r, y), ( (x, y + 1), 0 ≤ y < d − 1, Ni (x, y) = (x − n mod r, 0), y = d − 1, ( (x, y − 1), 0 < y ≤ d − 1, Si (x, y) = (x + n mod r, d − 1), y = 0.
(15) (16) (17) (18)
Here E, W, Ni , Si denote east, west, north, and south moves. Remark 1. It is important that the x-coordinate changes by −n only when the +i move wraps from row d − 1 to row 0. It is not correct to subtract n at every vertical step. Lemma 1. The wrap shift n is divisible by d. 4
Proof. Write a = da1 and b = db1 . Then n ≡ av − bu = d(a1 v − b1 u)
(mod r).
(19)
Also, a2 + b 2 = d(a21 + b21 ), r= d so r is divisible by d. Hence the chosen residue n modulo r is a multiple of d.
4
(20) □
The Unified Switching Construction
The construction begins with all horizontal edges. These edges form d disjoint row cycles, each of length r. The construction then performs d − 1 local switches. For d = 1, the switch set is empty. The horizontal cycle and vertical cycle are already Hamiltonian, so the construction reduces to the known coprime case. For d > 1, define for every q = 1, 2, . . . , d − 1 (21) the switching column aq = q − 1.
(22)
Aq = (aq , q) = (q − 1, q), Bq = (aq + 1, q) = (q, q), Cq = Aq + i, Dq = Bq + i.
(23) (24) (25) (26)
Define the four switch vertices
The switch removes the two horizontal edges Aq Bq ,
Cq Dq ,
(27)
Aq Cq ,
Bq Dq .
(28)
and inserts the two vertical edges
Let R be the set of removed horizontal edges and S the set of inserted vertical edges: R = {Aq Bq , Cq Dq : 1 ≤ q ≤ d − 1}, S = {Aq Cq , Bq Dq : 1 ≤ q ≤ d − 1}.
(29) (30)
Let Eh be the set of all horizontal edges and Ev the set of all vertical edges. Define E(H1 ) = (Eh \ R) ∪ S,
(31)
E(H2 ) = (Ev \ S) ∪ R.
(32)
and
5
Figure 1: Local switch sq . The two dashed horizontal edges Aq Bq and Cq Dq are removed from the horizontal construction of H1 and are assigned to H2 . The two solid vertical edges Aq Cq and Bq Dq are inserted into H1 and excluded from H2 . Equivalently, H2 is the edge-complement of H1 inside Gα , using precisely the graph edges not selected by H1 . Intuitively, Gα is 4-regular and H1 uses exactly two incident edges at every vertex; the remaining two incident edges at each vertex form the complementary 2-regular graph H2 . Figure 1 illustrates the local switch operation. The dashed horizontal edges are removed from H1 and become part of H2 , while the solid vertical switch edges are inserted into H1 and removed from H2 . The global effect of the same switch family is summarized in Fig. 2. In the horizontal structure, the switches splice the d row cycles into one Hamiltonian cycle H1 . In the complementary vertical structure, the corresponding exchanged edges splice the vertical cycles into one Hamiltonian cycle H2 .
5
Correctness Proof
We first state a basic cycle-splicing fact. Lemma 2. (Two-edge splicing) Let C1 and C2 be two vertex-disjoint cycles. Suppose 6
Figure 2: Conceptual effect of the unified switch rule. The switches s1 , . . . , sd−1 splice the horizontal row cycles into the Hamiltonian cycle H1 , while the complementary exchanged edges splice the vertical cycles into the Hamiltonian cycle H2 . xy is an edge of C1 and uv is an edge of C2 . Removing xy and uv and adding xu and yv produces one cycle containing all vertices of C1 ∪ C2 , provided that the added edges are valid graph edges. Proof. Removing one edge from each cycle turns C1 and C2 into two paths. The two added edges connect the two paths end-to-end, producing one cycle. No vertex is removed or repeated. □ Lemma 3. For 1 ≤ q ≤ d − 1, each local switch is valid, and no two switches use the same removed or inserted edge. Proof. By construction, Aq and Bq differ by +1, so Aq Bq is horizontal. Also, Cq = Aq + i and Dq = Bq + i. Therefore, Cq and Dq differ by +1, so Cq Dq is horizontal. The edges Aq Cq and Bq Dq are vertical by definition. The removed edge Aq Bq lies on row q, while Cq Dq lies on row q +1 (mod d). The formula aq = q − 1 gives distinct switch positions across the row adjacencies. The inserted vertical edges have lower endpoints Aq and Bq , which are distinct for different q. Hence the inserted
7
edges are distinct. The only row that appears in two consecutive switches is handled at different horizontal columns, so the removed horizontal edges are also distinct. □ Lemma 4. For d > 1, the graph H1 is a Hamiltonian cycle. Proof. Before switching, Eh consists of d disjoint row cycles: C0 , C1 , . . . , Cd−1 ,
(33)
where Cy denotes the horizontal cycle in row y. The switch at row q removes one horizontal edge from row q and one horizontal edge from row q + 1 for 1 ≤ q ≤ d − 2. It then inserts two vertical edges between these two rows. Therefore, for 1 ≤ q ≤ d − 2, switch sq splices Cq with Cq+1 . For the last switch, q = d − 1, the vertices Cd−1 = Ad−1 + i and Dd−1 = Bd−1 + i are obtained through the vertical wrap from row d − 1 to row 0; hence sd−1 splices Cd−1 with C0 . Thus the row-cycle adjacencies created by the switches are switch row cycles spliced s1 C1 ↔ C2 C2 ↔ C3 s2 .. .. . . Cd−2 ↔ Cd−1 sd−2 sd−1 Cd−1 ↔ C0 .
(34)
These d − 1 adjacencies form a connected tree on the d row cycles. Equivalently, the row cycles are connected in the order C0 − Cd−1 − Cd−2 − · · · − C2 − C1 .
(35)
By Lemma 2, each switch reduces the number of cycles by one. Starting from d cycles and applying d − 1 switches leaves exactly one cycle. Since the switches preserve degree two and keep all vertices, the resulting cycle contains all N vertices. Therefore H1 is Hamiltonian. □ Lemma 5. The vertical cycles before switching are indexed by x mod d. Proof. A non-wrap vertical step changes (x, y) to (x, y + 1) and therefore preserves x mod d. A wrap vertical step changes (x, d − 1) to (x − n, 0). By Lemma 1, n is divisible by d, so x − n ≡ x (mod d). Hence every vertical step preserves x mod d, and each vertical component is contained in one residue class modulo d. It remains to show that each residue class gives one cycle, not several smaller cycles. Write (36) a = da1 , b = db1 , r = d(a21 + b21 ). Since ua + vb = d, we have ua1 + vb1 = 1,
(37)
so gcd(a1 , b1 ) = 1. Also write n = dn′ and r = dr′ , where n′ = a1 v − b1 u,
r′ = a21 + b21 . 8
(38)
We claim that gcd(n′ , r′ ) = 1.
(39)
Indeed, if a prime p divides both n′ = a1 v − b1 u and r′ = a21 + b21 , then using ua1 + vb1 = 1 gives a1 = a1 (ua1 + vb1 ) = ua21 + va1 b1 ≡ −ub21 + va1 b1 = b1 (a1 v − b1 u) ≡ 0 (mod p).
(40)
Similarly, b1 ≡ 0 (mod p), contradicting gcd(a1 , b1 ) = 1. Hence gcd(n′ , r′ ) = 1. Now fix a residue class c mod d. Its columns are c, c + d, c + 2d, . . . , c + (r′ − 1)d.
(41)
After one full vertical traversal through the d rows, the wrap changes x by −n = −dn′ , which is the step −n′ on the r′ columns inside the fixed residue class. Since gcd(n′ , r′ ) = 1, repeated full wraps visit all r′ columns in that residue class before returning. Each such column contributes all d rows, so the component has dr′ = r vertices. Therefore each residue class x mod d is exactly one vertical cycle of length r, and there are precisely d such cycles. □ Lemma 6. For d > 1, the graph H2 is a Hamiltonian cycle. Proof. Before switching, Ev consists of d vertical cycles. By Lemma 5, these cycles are indexed by x mod d. Consider the switch for a fixed q, where 1 ≤ q ≤ d − 1. The horizontal edge Aq Bq = ((q − 1, q), (q, q))
(42)
connects the vertical-cycle index q − 1 to the vertical-cycle index q. Since Cq = Aq + i and Dq = Bq + i, adding i preserves the x-coordinate modulo d by Lemma 5. Hence Cq Dq also connects the vertical-cycle index q − 1 to the vertical-cycle index q. In H2 , the two vertical edges Aq Cq and Bq Dq are removed from the corresponding vertical cycles, while the two horizontal edges Aq Bq and Cq Dq are inserted. By Lemma 2, this splices the two vertical cycles indexed by q − 1 and q. As q ranges from 1 to d − 1, the complement switches join the vertical-cycle indices through 0 − 1 − 2 − · · · − (d − 1), (43) which is a tree on the d vertical cycles. Therefore the d − 1 complement switches reduce the d vertical cycles to one cycle. Since the switches preserve degree two and all vertices remain present, H2 is Hamiltonian. □ Lemma 7. For every nondegenerate Gaussian network with N > 2, the constructed graphs H1 and H2 are edge-disjoint and their edge sets partition E(Gα ). Proof. Let Eh be the set of edges generated by ±1, and let Ev be the set of edges generated by ±i. Since N > 2, no undirected edge can be both horizontal and vertical. Otherwise, 9
one would have ±1 ≡ ±i (mod α), so α would divide one of 1 + i or 1 − i, whose norm is 2, contradicting N (α) = N > 2. Hence Eh ∩ Ev = ∅.
(44)
E(Gα ) = Eh ∪ Ev .
(45)
Also, The switch construction chooses R ⊆ Eh and S ⊆ Ev and defines E(H1 ) = (Eh \ R) ∪ S,
(46)
E(H2 ) = (Ev \ S) ∪ R.
(47)
while Thus every horizontal edge is placed in exactly one of H1 and H2 : the edges in R go to H2 , and the edges in Eh \ R remain in H1 . Similarly, every vertical edge is placed in exactly one of H1 and H2 : the edges in S go to H1 , and the edges in Ev \ S remain in H2 . Therefore E(H1 ) ∩ E(H2 ) = ∅
(48)
E(H1 ) ∪ E(H2 ) = E(Gα ).
(49)
and □ Theorem 1. Let α = a + bi with 0 < a ≤ b, let N = a2 + b2 > 2, and let Gα be the corresponding nondegenerate Gaussian network. The construction defined by q = 1, 2, . . . , d − 1,
aq = q − 1,
(50)
where d = gcd(a, b), constructs two edge-disjoint Hamiltonian cycles in Gα . It applies uniformly to d = 1, d > 1, odd d, and even d. Proof. If d = 1, no switch is used. The horizontal edges form one Hamiltonian cycle and the vertical edges form a second Hamiltonian cycle, as in the known coprime case [2]. These cycles are edge-disjoint because they use different dimensions. Now assume d > 1. Lemma 4 shows that H1 is Hamiltonian. Lemma 6 shows that H2 is Hamiltonian. Lemma 7 shows that their edge sets are disjoint and partition the edge set of Gα : E(H1 ) ∩ E(H2 ) = ∅, E(H1 ) ∪ E(H2 ) = E(Gα ). (51) Thus, H1 and H2 are two edge-disjoint Hamiltonian cycles. The proof does not depend on whether d is odd or even. □ Corollary 1. For d > 1, the two cycles have the following edge-type counts: |E(H1 ) ∩ Eh | = N − 2(d − 1), |E(H1 ) ∩ Ev | = 2(d − 1), |E(H2 ) ∩ Eh | = 2(d − 1), |E(H2 ) ∩ Ev | = N − 2(d − 1). 10
(52) (53) (54) (55)
Proof. Each of the d − 1 switches removes two horizontal edges from H1 and inserts two vertical edges into H1 . Thus H1 contains N − 2(d − 1) horizontal edges and 2(d − 1) vertical edges. Since H2 is the complement, it contains the opposite counts. □
6
Algorithms
This section gives explicit algorithms for constructing the two Hamiltonian cycles. Algorithm 1 constructs the switch sets. Algorithm 2 gives constant-time membership for the two cycles. Algorithm 3 lists the Hamiltonian-cycle order. Algorithm 1. ConstructSwitchSets(a, b) Require: Generator α = a + bi, 0 < a ≤ b Ensure: Removed set R and inserted set S 1: d ← gcd(a, b); N ← a2 + b2 ; r ← N/d 2: Find u, v such that ua + vb = d 3: n ← av − bu (mod r) 4: R ← ∅, S ← ∅ 5: for q = 1 to d − 1 do 6: aq ← q − 1 7: A ← (aq , q); B ← (aq + 1, q) 8: C ← A + i using the rectangle move 9: D ← B + i using the rectangle move 10: R ← R ∪ {AB, CD} 11: S ← S ∪ {AC, BD} 12: end for 13: return R, S
Algorithm 2. CycleNeighbors(v, R, S) Require: Vertex v, switch sets R, S Ensure: The two neighbors of v in H1 and in H2 1: NG (v) ← {v ± 1, v ± i} 2: N1 ← ∅; N2 ← ∅ 3: for each w ∈ NG (v) do 4: e ← {v, w} 5: if e ∈ S or (e is horizontal and e ∈ / R) then 6: N1 ← N1 ∪ {w} 7: else 8: N2 ← N2 ∪ {w} 9: end if 10: end for 11: return N1 , N2
11
Algorithm 3. TraverseCycle(s, NC ) Require: Start vertex s, neighbor function NC (·) for H1 or H2 Ensure: Vertex order of the Hamiltonian cycle 1: L ← [s]; prev ← ⊥; cur ← s 2: repeat 3: Let NC (cur) = {z1 , z2 } 4: if z1 ̸= prev then 5: next ← z1 6: else 7: next ← z2 8: end if 9: prev ← cur; cur ← next 10: if cur ̸= s then 11: append cur to L 12: end if 13: until cur = s 14: return L
6.1
Complexity
The switch rule computes each switch using a constant number of arithmetic operations. Therefore, constructing the switch sets takes O(d) time. Since each Hamiltonian cycle has N edges, listing either cycle takes O(N ) time. The total cycle-generation time is therefore O(N ), and the local rule for each switch is constant time.
7
Examples
7.1
Example 1: The Coprime Case α = 3 + 5i
Here d = gcd(3, 5) = 1,
N = 34.
(56)
The switch set is empty. The first Hamiltonian cycle is obtained by repeatedly adding 1, and the second is obtained by repeatedly adding i. Thus, the construction reduces exactly to the previously known d = 1 case.
7.2
Example 2: The Non-Coprime Case α = 4 + 4i
Here d = 4,
N = 32,
r = 8.
(57)
(q, aq ) = (1, 0), (2, 1), (3, 2).
(58)
The switches are
12
The first two switches connect consecutive rows without wrap-around: (0, 1)(1, 1), (0, 2)(1, 2), (1, 2)(2, 2), (1, 3)(2, 3).
(59) (60)
The final switch uses the wrap from row 3 to row 0: A3 = (2, 3),
B3 = (3, 3),
(61)
C3 = (6, 0),
D3 = (7, 0).
(62)
and because n = 4, This produces H1 : 26 horizontal edges + 6 vertical edges,
(63)
H2 : 6 horizontal edges + 26 vertical edges.
(64)
and The switch data for this example are q aq Aq , Bq Cq , Dq 1 0 (0, 1), (1, 1) (0, 2), (1, 2) 2 1 (1, 2), (2, 2) (1, 3), (2, 3) 3 2 (2, 3), (3, 3) (6, 0), (7, 0).
(65)
The last switch is the wrap switch from row 3 to row 0.
(a) H1
(b) H2
Figure 3: The two Hamiltonian cycles for G4+4i shown separately. (a) The cycle H1 is obtained from the horizontal row-cycle structure by applying the switch operations; the red edges are the inserted vertical switch edges. (b) The cycle H2 is obtained from the complementary vertical structure; the red edges are the horizontal switch edges removed from H1 and assigned to H2 .
13
Figure 4: Combined drawing of the two edge-disjoint Hamiltonian cycles in G4+4i . The cycle H1 is drawn in blue and the cycle H2 is drawn in red. The two cycles have no common graph edge, i.e., E(H1 ) ∩ E(H2 ) = ∅. Crossings in the drawing are visual crossings only and do not represent shared edges. Figures 3 and 4 illustrate the complete construction for G4+4i . Figure 3 shows the two Hamiltonian cycles separately: H1 uses the switched horizontal structure, while H2 uses the complementary vertical structure. Figure 4 draws the two cycles together, with H1 in blue and H2 in red. The combined drawing emphasizes edge-disjointness: any crossings are geometric crossings in the drawing only and are not shared graph edges.
7.3
Example 3: An Odd Non-Coprime Case α = 5 + 10i
For α = 5 + 10i, d = 5,
N = 125,
r = 25.
(66)
(q, aq ) = (1, 0), (2, 1), (3, 2), (4, 3).
(67)
|H1 | = |H2 | = 125,
(68)
H1 : 117 horizontal + 8 vertical,
(69)
The switch sequence is The validation gives and the edge decomposition is
14
H2 : 8 horizontal + 117 vertical.
8
(70)
Experimental Validation
A Python validation program was written to test the construction. For each generator α = a + bi, the program computes d, r, n, constructs the switch sets, verifies the degree of every vertex in H1 and H2 , traverses each cycle, and confirms that each traversal visits all N vertices exactly once. It also records edge-type counts and runtime. The degenerate network α = 1 + i with N = 2 is excluded because the four formal directions collapse to a single undirected edge. The validator checks four correctness conditions for every nondegenerate input. First, every vertex has degree two in H1 and degree two in H2 . Second, a traversal of H1 returns one cycle containing all N vertices, and the same condition is checked independently for H2 . Third, the edge sets are tested for disjointness, i.e., E(H1 ) ∩ E(H2 ) = ∅. Finally, the measured horizontal and vertical edge counts are compared with the closed-form counts in Corollary 1.
8.1
Validation Scope
The validation included: • 18 representative cases covering d = 1, d > 1, odd d, even d, small networks, and large networks; • exhaustive validation for all 1 ≤ a ≤ b ≤ 100; • large-scale validation up to N = 3,250,000. Table 2: Representative validation of the closed-form EDHC construction. α 3 + 5i 4 + 4i 3 + 6i 5 + 10i 6 + 6i 6 + 8i 8 + 8i 8 + 12i 10 + 15i 12 + 12i 15 + 20i 20 + 30i 25 + 35i 50 + 50i 60 + 80i 100 + 100i 100 + 150i 200 + 300i
d 1 4 3 5 6 2 8 4 5 12 5 10 5 50 20 100 50 100
r 34 8 15 25 12 50 16 52 65 24 125 130 370 100 500 200 650 1300
N 34 32 45 125 72 100 128 208 325 288 625 1300 1850 5000 10000 20000 32500 130000
15
|H1 | 34 32 45 125 72 100 128 208 325 288 625 1300 1850 5000 10000 20000 32500 130000
|H2 | 34 32 45 125 72 100 128 208 325 288 625 1300 1850 5000 10000 20000 32500 130000
Result Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes Yes
Table 3: Edge-type decomposition of the two Hamiltonian cycles. α 3 + 5i 4 + 4i 3 + 6i 5 + 10i 6 + 6i 6 + 8i 8 + 8i 8 + 12i 10 + 15i 12 + 12i 20 + 30i 50 + 50i 100 + 100i 200 + 300i
d 1 4 3 5 6 2 8 4 5 12 10 50 100 100
H1h 34 26 41 117 62 98 114 202 317 266 1282 4902 19802 129802
H1v 0 6 4 8 10 2 14 6 8 22 18 98 198 198
H2h 0 6 4 8 10 2 14 6 8 22 18 98 198 198
H2v 34 26 41 117 62 98 114 202 317 266 1282 4902 19802 129802
2(d − 1) 0 6 4 8 10 2 14 6 8 22 18 98 198 198
Table 4: Aggregate correctness summary. Category All Exhaustive 1 ≤ a ≤ b ≤ 100 Large scale Representative d=1 d>1 Odd d Even d
8.2
Cases 5076 5050 8 18 3045 2031 3781 1295
Checked 5075 5049 8 18 3044 2031 3780 1295
Successes 5075 5049 8 18 3044 2031 3780 1295
Failures 0 0 0 0 0 0 0 0
Interpretation of the Experiments
The exhaustive test contains 5050 generator pairs with 1 ≤ a ≤ b ≤ 100. The only excluded pair is α = 1 + i, where N = 2. Therefore, 5049 nondegenerate exhaustive cases were checked and all passed. The validation also separately confirms the important categories d = 1, d > 1, odd d, and even d. The large-scale tests show linear behavior, because the validation time grows approximately proportionally with N . Table 5: Runtime scalability of the validation procedure. α 100 + 100i 100 + 150i 200 + 200i 200 + 300i 500 + 500i 500 + 750i 1000 + 1000i 1000 + 1500i
d 100 50 200 100 500 250 1000 500
N 20000 32500 80000 130000 500000 812500 2000000 3250000
16
Total ms 521.907 892.941 2223.681 5310.403 16605.924 26680.321 68336.990 112296.254
µs/node 26.095350 27.475108 27.796012 40.849254 33.211848 32.837318 34.168495 34.552694
9
Discussion
The construction has two useful interpretations. First, it is a unifying theorem: the same rule covers both the old coprime case and the non-coprime case. Second, it is an algorithmic proof: the switches are not found by search and are not described by long tables. They are given by one formula. The key design choice is to omit the row adjacency 0 ↔ 1 from the horizontal-cycle splicing and instead include the wrap adjacency (d − 1) ↔ 0. This makes H1 join rows through 0 − (d − 1) − (d − 2) − · · · − 1, (71) while the complement H2 joins vertical cycle indices through 0 − 1 − 2 − · · · − (d − 1).
(72)
Thus, one set of switches creates two different spanning splice trees: one for the horizontal cycles and one for the vertical cycles.
10
Conclusion
This paper presented a unified constant-time switch rule for constructing two edge-disjoint Hamiltonian cycles in Gaussian networks. The construction covers the known coprime case d = 1 and the non-coprime case d > 1 in a single framework. It also removes the need for separate odd/even d cases. The rule is simply to switch row adjacency q at column aq = q − 1 for q = 1, . . . , d − 1. The switched horizontal graph is one Hamiltonian cycle, and its edge-complement is the second Hamiltonian cycle; the two cycles are edge-disjoint by construction. The construction is compact, implementable, and linear-time for explicit cycle generation. Exhaustive and large-scale validation confirmed the result for all tested nondegenerate Gaussian networks, including all generators with 1 ≤ a ≤ b ≤ 100 and large networks up to 3,250,000 vertices.
Funding This research received no external funding.
Data Availability The validation data and source code generated for this study are available from the corresponding author upon reasonable request and can be provided as supplementary material during peer review.
Conflicts of Interest The author declares no conflicts of interest. 17
Acknowledgments The author would like to acknowledge the support of Kuwait University and its Computer Science Department and would like to thank the researchers whose previous work on Gaussian networks and edge-disjoint Hamiltonian cycles motivated this unified construction.
References [1] Martı́nez, C.; Beivide, R.; Stafford, E.; Moretó, M.; Gabidulin, E.M. Modeling toroidal networks with the Gaussian integers. IEEE Trans. Comput. 2008, 57, 1046–1056. [2] Flahive, M.; Bose, B. The topology of Gaussian and Eisenstein–Jacobi interconnection networks. IEEE Trans. Parallel Distrib. Syst. 2010, 21, 1132–1142. [3] Albader, B.; Bose, B. Edge disjoint Hamiltonian cycles in Gaussian networks. IEEE Trans. Comput. 2016, 65, 315–321. https://doi.org/10.1109/TC.2015.2409843. [4] Bae, M.M.; Bose, B. Edge-disjoint Hamiltonian cycles in k-ary n-cubes and hypercubes. IEEE Trans. Comput. 2003, 52, 1271–1284. [5] Barth, D.; Raspaud, A. Two edge-disjoint Hamiltonian cycles in butterfly graphs. Inf. Process. Lett. 1994, 51, 175–179. [6] Hung, R.-W. Constructing two edge-disjoint Hamiltonian cycles in twisted cubes. Theor. Comput. Sci. 2011, 412, 4523–4531. [7] Hung, R.-W. Constructing two edge-disjoint Hamiltonian cycles in locally twisted cubes. Theor. Comput. Sci. 2011, 412, 2246–2254. [8] Hung, J.-H. Edge-disjoint Hamiltonian cycles in augmented cubes. Theor. Comput. Sci. 2015, 575, 1–9. [9] Pai, K.-J.; Wu, R.-Y.; Tan, J.M. Three edge-disjoint Hamiltonian cycles in folded locally twisted cubes and folded crossed cubes with applications to all-to-all broadcasting. Mathematics 2023, 11, 3384. [10] Cheng, B.-L.; Tan, J.M.; Pai, K.-J. Edge-disjoint Hamiltonian cycles in balanced hypercubes with applications to fault-tolerant data broadcasting. Appl. Sci. 2024, 14, 3232. [11] Pai, K.-J.; Tan, J.M.; Hsu, L.-H. Constructing two edge-disjoint Hamiltonian cycles and two equal node-disjoint cycles in BCube. Mathematics 2026, 14, 232. [12] Yang, D.-W.; Chen, X.-B. Symmetric property and edge-disjoint Hamiltonian cycles in Cayley graphs. Appl. Math. Comput. 2023, 455, 128113. [13] Wu, W.; Chen, Y.; Fan, J. Embedding spanning disjoint cycles in hypercube-like networks. Axioms 2023, 12, 861. 18
[14] Duato, J.; Yalamanchili, S.; Ni, L. Interconnection Networks: An Engineering Approach; Morgan Kaufmann: San Francisco, CA, USA, 2003. [15] Leighton, F.T. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes; Morgan Kaufmann: San Mateo, CA, USA, 1992.
19