A Unified Constant-Time Switch Rule for Constructing Edge-Disjoint Hamiltonian Cycles in Gaussian Networks
2026-06-15 • Distributed, Parallel, and Cluster Computing
Distributed, Parallel, and Cluster ComputingDiscrete MathematicsInformation TheoryNetworking and Internet Architecture
AI summaryⓘ
The authors study Gaussian networks, which are special grid-like structures based on complex numbers. They focus on finding two separate loops (called Hamiltonian cycles) that each visit every point once without sharing edges. Earlier methods worked only when certain number conditions were met or used complicated tables. The authors provide a simpler, general recipe that works for all cases, using a simple pattern to switch connections in the network and prove it always creates two perfect loops. They confirmed their method works for very large networks through extensive testing.
Gaussian networksHamiltonian cycleGaussian integersEdge-disjoint cyclesGraph theoryInterconnection networksGCD (Greatest common divisor)Residue classesCycle decompositionAlgorithmic construction
Authors
Bader Albader
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=(a^2+b^2)/d$ columns, the construction uses a constant-time local switch rule for each $q=1,2,\ldots,d-1$ at column $a_q=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=a^2+b^2$. Exhaustive validation for all $1\leq a\leq b\leq 100$, excluding only the degenerate $N=2$ network, and large-scale validation up to $N=3{,}250{,}000$ confirm the construction.