Generalized shuffle-exchange digraphs: Hamiltonian properties

The k-ary n-dimensional shuffle-exchange directed network S(k, n) consists of kⁿ nodes such that each node is represented as an k-ary n-tuple vector, a₁a₂···a_n, where a_i is in [0, k-1]. Node a₁a₂···a_n is adjacent to node a₂a₃···a_na₁ (one shuffle link) and k-1 other nodes a₁a₂···a_n-1b, where b∈[0, k-1] and b≠a_n (k-1 exchange links). S(k, n) have been widely used as topologies for VLSI networks, parallel architectures, and communication systems. However, since S(k, n) does not exist for the number of nodes between kⁿ and kⁿ⁺¹, Liu and Hsu have recently proposed a class of digraphs GS(k, N), which generalized S(k, n) to any number N of nodes. They also showed that GS(k, N) retains all the nice properties of S(k, n). In this paper, we survey these combinatorial properties and study Hamiltonian properties of GS(k, N). In particular, we have successfully obtained Hamiltonian circuit for GS(k, k(k+1)) for any k>2.