کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
395906 | 666091 | 2009 | 11 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Long paths and cycles in hypercubes with faulty vertices Long paths and cycles in hypercubes with faulty vertices](/preview/png/395906.png)
A fault-free path in the nn-dimensional hypercube QnQn with ff faulty vertices is said to be long if it has length at least 2n-2f-22n-2f-2. Similarly, a fault-free cycle in QnQn is long if it has length at least 2n-2f2n-2f. If all faulty vertices are from the same bipartite class of QnQn, such length is the best possible. We show that for every set of at most 2n-42n-4 faulty vertices in QnQn and every two fault-free vertices uu and vv satisfying a simple necessary condition on neighbors of uu and vv, there exists a long fault-free path between uu and vv. This number of faulty vertices is tight and improves the previously known results. Furthermore, we show for every set of at most n2/10+n/2+1n2/10+n/2+1 faulty vertices in QnQn where n⩾15n⩾15 that QnQn has a long fault-free cycle. This is a first quadratic bound, which is known to be asymptotically optimal.
Journal: Information Sciences - Volume 179, Issue 20, 29 September 2009, Pages 3634–3644