TY - JOUR

T1 - Extended fault-tolerant cycle embedding in faulty hypercubes

AU - Hsieh, Sun Yuan

AU - Chang, Nai Wen

PY - 2009/11/16

Y1 - 2009/11/16

N2 - We consider fault-tolerant embedding, where an-dimensional faulty hypercube, denoted by Qn, acts as the host graph, and the longest fault-free cycle represents the guest graph. Let Fv be a set of faulty nodes in Qn. Also, let Fe be a set of faulty edges in which at least one end-node of each edge is faulty, and let Fe be a set of faulty edges in which the end-nodes of each edge are both fault-free. An edge Qn in is said to be critical if it is either fault-free or in Fe. In this paper, we prove that there exists a fault-free cycle of length at least 2n-2|Fv| in Qn (n≥3) with |Fe| ≤ 2n-5, and |Fv|+|Fe|≤2n-4, in which each node is incident to at least two critical edges. Our result improves on the previously best known results reported in the literature, where only faulty nodes or faulty edges are considered.

AB - We consider fault-tolerant embedding, where an-dimensional faulty hypercube, denoted by Qn, acts as the host graph, and the longest fault-free cycle represents the guest graph. Let Fv be a set of faulty nodes in Qn. Also, let Fe be a set of faulty edges in which at least one end-node of each edge is faulty, and let Fe be a set of faulty edges in which the end-nodes of each edge are both fault-free. An edge Qn in is said to be critical if it is either fault-free or in Fe. In this paper, we prove that there exists a fault-free cycle of length at least 2n-2|Fv| in Qn (n≥3) with |Fe| ≤ 2n-5, and |Fv|+|Fe|≤2n-4, in which each node is incident to at least two critical edges. Our result improves on the previously best known results reported in the literature, where only faulty nodes or faulty edges are considered.

UR - http://www.scopus.com/inward/record.url?scp=77957958516&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77957958516&partnerID=8YFLogxK

U2 - 10.1109/TR.2009.2034286

DO - 10.1109/TR.2009.2034286

M3 - Article

AN - SCOPUS:77957958516

SN - 0018-9529

VL - 58

SP - 702

EP - 710

JO - IEEE Transactions on Reliability

JF - IEEE Transactions on Reliability

IS - 4

M1 - 5332283

ER -