Cycle embedding in faulty enhanced hypercube networks

In recent three decades, several variants of the hypercube networks have been proposed to enhance the performance and reliability. The so called enhanced hypercube networks (denoted by Q_n,k) is one of the most versatile and efficient interconnection networks for the parallel computation, aiming to fully realize the potential of those networks where reliability, speed and tolerance are critical. In this paper, the properties related to cycles embedding in faulty Q_n,k have been investigated. This study demonstrates that when the number of fault nodes in Q_n,k is only one, if n and k have the same parity, then the cycles of every even length from 4 to 2ⁿ - 2 can be embedded in the faulty Q_n,k; if n and k have different parity, then the cycles of every even length from 4 to 2ⁿ - 2 and every odd length from n - k + 2 to 2ⁿ - 1 can be embedded in the faulty Q_n,k. When the number of fault links is no more than n - 1, in Q_n,k, if n and k have the same parity, then every non-fault link of Q_n,k lies on a cycle of every even length from 4 to 2ⁿ. These results show that with cycle embedding, the enhanced hypercube networks have very good fault tolerance and reliability as a topological structure of multi-computer networks.