Fault-tolerant cycles embedded in hypercubes with mixed link and node failures

✍ Scribed by Chang-Hsiung Tsai

• Publisher: Elsevier Science
• Year: 2008
• Tongue: English
• Weight: 282 KB
• Volume: 21
• Category: Article
• ISSN: 0893-9659
• DOI: 10.1016/j.aml.2007.08.012

✦ Synopsis

Let f e (respectively, f v ) denote the number of faulty edges (respectively, vertices) of an n-dimensional hypercube Q n . In this paper, we prove that every fault-free edge of Q n for n ≥ 3 lies on a fault-free cycle of every even length from 4 to 2 n -2 f v inclusive if f e + f v ≤ n -2. Furthermore, we also prove that Q n for n ≥ 5 contains a fault-free cycle of every even length from 4 to 2 n -2 f v inclusive if f e ≤ n -2 and f e + f v ≤ 2n -4. This result has better tolerance for the faulty components than the degree of the hypercube.