Longest Paths and Cycles in Faulty Hypercubes

C.-N. Hung, Y.-H. Chang, and C.-M. Sun (Taiwan)

Keywords

faulttolerant, hyperhamiltonianlaceable, hamiltonian laceable, hypercube.

Abstract

The length of all the previous fault-tolerant ring embed ding in the hypercube Qn is at most 2n − 2fv where fv is the number faulty vertices. In this paper, we con struct the fault-free cycle with 2n − 2|Fv| + 2 vertices in Qn − Fv where Fv is the faulty vertices set contains at least a black vertex and a white vertex with |Fv| ≤ n−1. We also construct the fault-free path with length at least 2n −2|Fv|+1(2n −2|Fv|) between every pair of vertices with the different(same) color of Qn − Fv where Fv con tains at least one black vertex and one white vertex with |Fv| ≤ n − 2.

Important Links:



Go Back