Symmetric Properties and Two Variants of Shuffle-Cubes
- 8 April 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Parallel and Distributed Systems
- Vol. 36 (6) , 1282-1293
Abstract
Li et al. in [Inf. Process. Lett. 77 (2001) 35–41] proposed the shuffle-cube $SQ_{n}$ , a hypercube variant, as an attractive interconnection network topology for massive parallel and distributed systems. Diameter and symmetry are two desirable measures of network performance in terms of transmission delay and routing algorithms. Almost all $n$ -regular hypercube variants of dimension $n$ have diameter not less than $n/2$ . The diameter of the shuffle-cube is approximately a quarter of the diameter of the hypercube of the same dimension, making it a competitive candidate network topology. By far, symmetric properties of the shuffle-cube remain unknown. In this paper, we show that $SQ_{n}$ is not vertex-transitive for $n> 2$ , which is not an appealing property in interconnection networks. This shortcoming limits the practical application of the shuffle-cube. To overcome this limitation, two novel variants of the shuffle-cube, namely simplified shuffle-cube $SSQ_{n}$ and balanced shuffle-cube $BSQ_{n}$ are introduced, and their vertex-transitivity are proved simultaneously. By proposing the shuffle-cube-like graph, we obtain that both $SSQ_{n}$ and $BSQ_{n}$ are maximally connected, implying high connectivity similar to the hypercube. Additionally, super-connectivity, a refined parameter of connectivity, of $SSQ_{n}$ and $BSQ_{n}$ are also determined. Then, by vertex-transitivity of $SSQ_{n}$ and $BSQ_{n}$ , routing algorithms of $SSQ_{n}$ and $BSQ_{n}$ are given for all $n> 2$ respectively. We show that both $SSQ_{n}$ and $BSQ_{n}$ possess Hamiltonian cycle embedding for all $n> 2$ , and we also show that $SSQ_{n}$ is Hamiltonian-connected. It is noticeable that each vertex of $SSQ_{n}$ is contained in exactly one clique of size four, making it also a viable interconnection topology for data center networking since each clique of size four can be viewed as an efficient local data processing cluster of the network. Finally, as a by-product of proving vertex-transitivity of $BSQ_{n}$ , we mend a flaw in the Property 3 in [IEEE Trans. Comput. 46 (1997) 484–490].
Keywords
All Related Versions
Funding Information
- National Natural Science Foundation of China (11801061, 12161002, 62371094)
- Central Government Funds of Guiding Local Scientific and Technological Development for Sichuan Province (2021ZYD0007)
This publication has 40 references indexed in Scilit:
- Reliability analysis based on the dual-CIST in shuffle-cubesApplied Mathematics and Computation, 2021
- Routing algorithms for the shuffle-exchange permutation networkThe Journal of Supercomputing, 2021
- Super connectivity of balanced hypercubesApplied Mathematics and Computation, 2012
- The conditional diagnosability of shuffle-cubesJournal of Systems Science and Complexity, 2010
- Survey on path and cycle embedding in some networksFrontiers of Mathematics in China, 2009
- Augmented cubesNetworks, 2002
- Algebraic Graph Theory2001
- Cayley graphs and interconnection networks1997
- Symmetry in interconnection networks based on Cayley graphs of permutation groups: A surveyParallel Computing, 1993
- The twisted cube topology for multiprocessors: A study in network asymmetryJournal of Parallel and Distributed Computing, 1991