pith. sign in

arxiv: 2606.16892 · v1 · pith:UMVZCXYNnew · submitted 2026-06-15 · 💻 cs.DC · cs.DM· cs.IT· cs.NI· math.IT

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

Bader Albader This is my paper

Pith reviewed 2026-06-30 11:22 UTC · model grok-4.3

classification 💻 cs.DC cs.DMcs.ITcs.NImath.IT
keywords Gaussian networksHamiltonian cyclesedge-disjoint cyclesinterconnection networksGaussian integersswitch rulerectangular representation
0
0 comments X

The pith

A constant-time local switch at fixed columns partitions any Gaussian network into two edge-disjoint Hamiltonian cycles.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents a single closed-form rule that works for every generator alpha = a + bi, whether gcd(a,b) equals 1 or is larger than 1. In the rectangular grid layout that has d rows, the rule performs a local edge swap at each of d-1 designated columns; each swap replaces two horizontal edges with two vertical edges. The modified horizontal paths become one Hamiltonian cycle and the untouched edges become the second cycle, so the entire edge set is covered exactly once. Because the rule needs no odd-even tables or separate proofs, it removes the case distinctions required by earlier constructions. The result supplies an explicit, linear-time way to obtain the two cycles for any network size.

Core claim

In the rectangular representation with d rows and r = (a squared plus b squared) divided by d columns, a constant-time local switch rule applied for each q from 1 to d-1 at column a_q equals q minus 1 removes two horizontal edges and inserts two vertical edges. The switched horizontal structure forms the first Hamiltonian cycle while its edge complement forms the second Hamiltonian cycle, partitioning the full edge set of the Gaussian network into two edge-disjoint Hamiltonian cycles. The same rule applies uniformly when d equals 1 and when d is greater than 1, and for both odd and even d.

What carries the argument

The local switch rule at column q-1 for each q=1 to d-1, which replaces two horizontal edges with two vertical edges to connect paths into a single cycle.

If this is right

  • The construction works for every generator without separate proofs for coprime and non-coprime cases.
  • Generating the switches takes O(d) time and listing the cycles takes O(N) time where N equals a squared plus b squared.
  • The two cycles together use every edge of the network exactly once.
  • The same rule covers both odd and even values of d.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The local-switch approach may extend to finding more than two edge-disjoint cycles when the network degree permits.
  • Because the rule is fully local, it could be executed in a distributed fashion on the network itself.
  • The rectangular layout plus switches gives an explicit embedding that might help with fault-tolerant routing or deadlock-free communication.

Load-bearing premise

The chosen switch positions always produce one connected cycle rather than several separate cycles.

What would settle it

Any pair a, b where applying the switches at columns 0 through d-2 yields more than one disjoint cycle in the rectangular layout.

Figures

Figures reproduced from arXiv: 2606.16892 by Bader Albader.

Figure 1
Figure 1. Figure 1: Local switch sq. The two dashed horizontal edges AqBq and CqDq are removed from the horizontal construction of H1 and are assigned to H2. The two solid vertical edges AqCq and BqDq 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… view at source ↗
Figure 2
Figure 2. Figure 2: Conceptual effect of the unified switch rule. The switches [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗
Figure 3
Figure 3. 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 [PITH_FULL_IMAGE:figures/full_fig_p013… view at source ↗
Figure 4
Figure 4. Figure 4: Combined drawing of the two edge-disjoint Hamiltonian cycles in [PITH_FULL_IMAGE:figures/full_fig_p014_4.png] view at source ↗
read the original abstract

Gaussian networks are degree-four symmetric interconnection networks defined over residue classes of Gaussian integers. Earlier work showed that when the generator $\alpha=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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper presents a unified construction for two edge-disjoint Hamiltonian cycles in Gaussian networks generated by α = a + bi (with d = gcd(a,b)), using a d-by-r rectangular layout (r = (a² + b²)/d) and a constant-time local switch rule applied at columns a_q = q-1 for q = 1 to d-1. Each switch replaces two horizontal edges with two vertical edges; the resulting switched graph is claimed to be one Hamiltonian cycle whose complement in the network is the second. The construction is O(d) to generate switches and O(N) to list the cycles (N = a² + b²), with exhaustive validation for all 1 ≤ a ≤ b ≤ 100 (except N=2) plus sampling to N = 3,250,000.

Significance. If the central claim holds, the result supplies a simple, case-free algorithmic rule that unifies prior constructions for both d=1 and d>1 (odd and even), replacing long node-sequence tables. The extensive computational validation (exhaustive small cases plus large-scale sampling) is a concrete strength that supports practical use and reduces the risk of counterexamples.

major comments (2)
  1. [Construction description (abstract and §3)] The assertion that the d-1 local switches at columns a_q = q-1 always produce a single connected N-cycle (rather than multiple disjoint 2-regular components) is load-bearing for the partition claim, yet the manuscript provides no explicit connectivity invariant or inductive argument; the result rests on the algebraic properties of the Gaussian integer generator and rectangular embedding, which are asserted but not derived in detail.
  2. [Validation section] Table of validation results (or equivalent section reporting exhaustive checks): while the checks cover all a,b ≤ 100 and large N, they do not constitute a proof for arbitrary d; a counterexample at some composite d > 100 would falsify the unified claim for the infinite family.
minor comments (2)
  1. [§2 or §3] Notation for the rectangular layout (d rows, r columns) and the precise definition of a_q should be introduced with an equation or diagram early in the construction section to improve readability.
  2. [Construction section] The time complexity statements (O(d) switch generation, O(N) cycle listing) are stated in the abstract but would benefit from a short complexity paragraph or pseudocode in the main text.

Simulated Author's Rebuttal

2 responses · 1 unresolved

We thank the referee for the positive assessment of the significance of our work and for the detailed comments. We address each major comment below and indicate whether revisions will be made.

read point-by-point responses

  1. Referee: [Construction description (abstract and §3)] The assertion that the d-1 local switches at columns a_q = q-1 always produce a single connected N-cycle (rather than multiple disjoint 2-regular components) is load-bearing for the partition claim, yet the manuscript provides no explicit connectivity invariant or inductive argument; the result rests on the algebraic properties of the Gaussian integer generator and rectangular embedding, which are asserted but not derived in detail.

    Authors: We acknowledge that the current manuscript asserts the connectivity based on the properties of the Gaussian integers and the rectangular layout without providing a detailed derivation or invariant. The construction is designed such that each switch connects the structure in a manner consistent with the group structure of the network. However, to address this, we will add a short paragraph in the revised version explaining the connectivity argument using the fact that the switches are applied at positions that preserve the overall cycle structure due to the symmetry of the embedding. This will make the reasoning more explicit without altering the core result. revision: partial

  2. Referee: [Validation section] Table of validation results (or equivalent section reporting exhaustive checks): while the checks cover all a,b ≤ 100 and large N, they do not constitute a proof for arbitrary d; a counterexample at some composite d > 100 would falsify the unified claim for the infinite family.

    Authors: We agree that the extensive computational validation, while covering all cases up to a,b ≤ 100 and sampling to much larger N, does not provide a mathematical proof for all d. Our paper presents the construction as a practical, unified rule supported by this validation, rather than claiming a complete proof. We believe the sampling to N=3,250,000 provides strong evidence against counterexamples, but we do not dispute that a formal proof would be desirable. No revision is planned for this point as the validation section accurately reports the checks performed. revision: no

standing simulated objections not resolved
  • We do not have a formal proof of the single-cycle property for arbitrary d beyond the computational evidence provided.

Circularity Check

0 steps flagged

No circularity; direct algorithmic construction with external validation

full rationale

The paper defines an explicit local switch rule at columns a_q = q-1 for q=1 to d-1 in the d-by-r rectangular layout derived from Gaussian integer generator α=a+bi. It asserts the resulting switched graph and its complement are Hamiltonian cycles, justified by the algebraic properties of the embedding plus exhaustive computational checks (all 1≤a≤b≤100 except N=2, plus sampling to N=3.25M). No step reduces a claimed result to a fitted parameter, self-definition, or self-citation chain; the construction is presented as a closed-form rule whose correctness is externally verified rather than tautological. The connectivity claim is a substantive assertion, not a renaming or redefinition of inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the standard definition of Gaussian networks as degree-4 symmetric graphs over Gaussian integer residues and on the algebraic properties that make the chosen rectangular layout and switch columns produce cycles; no free parameters or invented entities are introduced.

axioms (1)
  • domain assumption Gaussian networks are degree-four symmetric interconnection networks defined over residue classes of Gaussian integers when gcd(a,b)=d.
    This is the foundational definition invoked throughout the construction.

pith-pipeline@v0.9.1-grok · 5829 in / 1347 out tokens · 40061 ms · 2026-06-30T11:22:09.282869+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

15 extracted references · 1 canonical work pages

  1. [1]

    Modeling toroidal networks with the Gaussian integers.IEEE Trans

    Mart´ ınez, C.; Beivide, R.; Stafford, E.; Moret´ o, M.; Gabidulin, E.M. Modeling toroidal networks with the Gaussian integers.IEEE Trans. Comput.2008,57, 1046–1056

    2008

  2. [2]

    The topology of Gaussian and Eisenstein–Jacobi interconnection networks.IEEE Trans

    Flahive, M.; Bose, B. The topology of Gaussian and Eisenstein–Jacobi interconnection networks.IEEE Trans. Parallel Distrib. Syst.2010,21, 1132–1142

    2010

  3. [3]

    Edge disjoint Hamiltonian cycles in Gaussian networks.IEEE Trans

    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

    work page doi:10.1109/tc.2015.2409843 2016

  4. [4]

    Edge-disjoint Hamiltonian cycles ink-aryn-cubes and hypercubes

    Bae, M.M.; Bose, B. Edge-disjoint Hamiltonian cycles ink-aryn-cubes and hypercubes. IEEE Trans. Comput.2003,52, 1271–1284

    2003

  5. [5]

    Two edge-disjoint Hamiltonian cycles in butterfly graphs.Inf

    Barth, D.; Raspaud, A. Two edge-disjoint Hamiltonian cycles in butterfly graphs.Inf. Process. Lett.1994,51, 175–179

    1994

  6. [6]

    Constructing two edge-disjoint Hamiltonian cycles in twisted cubes

    Hung, R.-W. Constructing two edge-disjoint Hamiltonian cycles in twisted cubes. Theor. Comput. Sci.2011,412, 4523–4531

    2011

  7. [7]

    Constructing two edge-disjoint Hamiltonian cycles in locally twisted cubes.Theor

    Hung, R.-W. Constructing two edge-disjoint Hamiltonian cycles in locally twisted cubes.Theor. Comput. Sci.2011,412, 2246–2254

    2011

  8. [8]

    Edge-disjoint Hamiltonian cycles in augmented cubes.Theor

    Hung, J.-H. Edge-disjoint Hamiltonian cycles in augmented cubes.Theor. Comput. Sci.2015,575, 1–9

    2015

  9. [9]

    Three edge-disjoint Hamiltonian cycles in folded locally twisted cubes and folded crossed cubes with applications to all-to-all broad- casting.Mathematics2023,11, 3384

    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 broad- casting.Mathematics2023,11, 3384

  10. [10]

    Edge-disjoint Hamiltonian cycles in balanced hy- percubes with applications to fault-tolerant data broadcasting.Appl

    Cheng, B.-L.; Tan, J.M.; Pai, K.-J. Edge-disjoint Hamiltonian cycles in balanced hy- percubes with applications to fault-tolerant data broadcasting.Appl. Sci.2024,14, 3232

    2024

  11. [11]

    Constructing two edge-disjoint Hamiltonian cycles and two equal node-disjoint cycles in BCube.Mathematics2026,14, 232

    Pai, K.-J.; Tan, J.M.; Hsu, L.-H. Constructing two edge-disjoint Hamiltonian cycles and two equal node-disjoint cycles in BCube.Mathematics2026,14, 232

  12. [12]

    Symmetric property and edge-disjoint Hamiltonian cycles in Cayley graphs.Appl

    Yang, D.-W.; Chen, X.-B. Symmetric property and edge-disjoint Hamiltonian cycles in Cayley graphs.Appl. Math. Comput.2023,455, 128113

    2023

  13. [13]

    Embedding spanning disjoint cycles in hypercube-like networks.Axioms2023,12, 861

    Wu, W.; Chen, Y.; Fan, J. Embedding spanning disjoint cycles in hypercube-like networks.Axioms2023,12, 861. 18

  14. [14]

    Duato, J.; Yalamanchili, S.; Ni, L.Interconnection Networks: An Engineering Ap- proach; Morgan Kaufmann: San Francisco, CA, USA, 2003

    2003

  15. [15]

    Leighton, F.T.Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes; Morgan Kaufmann: San Mateo, CA, USA, 1992. 19

    1992