A Unified Constant-Time Switch Rule for Constructing Edge-Disjoint Hamiltonian Cycles in Gaussian Networks

Abstract

Gaussian networks are degree-four symmetric interconnection networks defined over residue classes of Gaussian integers. Earlier work showed that when the generator $\hat{I}\pm =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,\dots ,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\le a\le b\le 100$, excluding only the degenerate $N=2$ network, and large-scale validation up to $N=3,250,000$ confirm the construction.

Preprint also available on Zenodo:https://doi.org/10.5281/zenodo.20690698