Some New Results on Fault-tolerant Cycles Embedding in Folded Hypercubes

Abstract

Under the conditions looser than previous works, this paper shows that the \( n \)-dimensional folded hypercube networks have a cycle with length at least \( 2^n – 2|F_v| \) when the number of faulty vertices and non-critical edges is at most \( 2n – 4 \), where \( |F_v| \) is the number of faulty vertices. Meanwhile, this paper proves that \( FQ_n \) contains a fault-free cycle with length at least \( 2^n – 2|F_v| \), under the constraints that (1) The number of both faulty nodes and faulty edges is no more than \( 2n – 3 \) and there is at least one faulty edge; (2) every node in \( FQ_n \) is incident to at least two fault-free links whose other end nodes are fault-free. These results have improved the present results with further theoretical evidence of the fact that \( FQ_n \) has excellent node-fault-tolerance and edge-fault-tolerance when used as a topology of large scale computer networks.