Symmetric properties and two variants of shuffle-cubes

2021/10/23 by Huazhong Lü, Kai Deng, Lü, Huazhong +2
Computer Science · Engineering · #05C90 #68R10 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Interconnection Networks and Systems #Low-power high-performance VLSI design #VLSI and FPGA Design Techniques

paper · pdf · doi:10.48550/arxiv.2110.13645

openalex publication_date 2021/10/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Li et al. in [Inf. Process. Lett. 77 (2001) 35--41] proposed the shuffle cube SQ_n as an attractive interconnection network topology for massive parallel and distributed systems. By far, symmetric properties of the shuffle cube remains unknown. In this paper, we show that SQ_n is not vertex-transitive for all n>2, which is not an appealing property in interconnection networks. To overcome this limitation, two novel vertex-transitive variants of the shuffle-cube, namely simplified shuffle-cube SSQ_n and balanced shuffle cube BSQ_n are introduced. Then, routing algorithms of SSQ_n and BSQ_n for all n>2 are given respectively. Furthermore, we show that both SSQ_n and BSQ_n possess Hamiltonian cycle embedding for all n>2. Finally, as a by-product, we mend a flaw in the Property 3 in [IEEE Trans. Comput. 46 (1997) 484--490].

Related

• Constructing Two Edge-Disjoint Hamiltonian Cycles and Two Equal Node-Disjoint Cycles in Twisted Cubes
• Routing linear permutations on Fibonacci and Lucas cubes
• Transitivity of Varietal Hypercube Networks
• The vertex-pancyclicity of the simplified shuffle-cube and the vertex-bipancyclicity of the balanced shuffle-cube
• Restricted routing and wide diameter of the cycle prefix network