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 $F{Q}_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 $F{Q}_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 $F{Q}_n$ has excellent node-fault-tolerance and edge-fault-tolerance when used as a topology of large scale computer networks.