Node-Pancyclic Properties of Biswapped Networks Based on Cycles in Their Factor Networks
Weidong Chen, Shan Ling · The Computer Journal · 2016
Cycle embedding in networks is one of the fundamental algorithmic issues in interconnection networks. Biswapped networks are a family of composite interconnection networks, applicable to constructing massive parallel computers owing to their attractive attributes. Specifically, each biswapped network is built by taking 2n copies of some n-node factor network as modules and connecting them in a simple inter-module connectivity rule. In this paper, the problem of embedding cycles of various lengths in a biswapped network is investigated based on a given cycle of length l≥3 in its factor network. We propose a simple method to address the problem. Using the method, one easily constructs cycles of all even lengths ranging from 8 to 2l2, and also cycles of all odd lengths ranging from l+6 to 2l2−1 for l being odd in the biswapped network. Together with the known property that a biswapped network inherits the node-symmetry of its factor network, these results indicate that if an n-node factor network is Hamiltonian, then the biswapped network enjoys 8-node-bipancyclicity, and also (n+5)-node-pancyclicity for n being odd. The basic technique behind our method comes from the observation that a cycle of a given length in the biswapped network can be constructed from two associated combined closed walks in the factor network. By constructing combined closed walks of different lengths in the factor network, we can build cycles of various lengths in the biswapped network. Our technique also can be used for embedding cycles in other composite networks, such as swapped networks and Cartesian product networks.