條件式容錯超立方體下的邊泛迴圈之研究

Abstract

Xu et al.先前曾提過相關的論文研究，證明了當N大於四時，在n維度的超力方體下若壞邊的數量小餘n-1時，通過任意指定的一個邊，仍可找到從6到2n這樣各種長度的迴圈，而限制條件在於並非所有壞邊皆集中在同一個點，意即每個點仍然存在有兩個好邊。 在這篇論文中，我們在相似的條件下，若壞邊不集中在同一個點，則壞邊個數能夠增加到2n-5個，且通過任意指定的一個邊，仍可找到長度從6到2n的各種的迴圈。此外我們仍證明了，當壞邊達到2n-4時，如此是無法被證明的，所以我們的結論是最佳的結果。

Xu et al. showed that for any set of faulty edges F of an n-dimensional hypercube Qn with |F|≦n-1, each edge of Qn-F lies on a cycle of every even length from 6 to 2n, n≧4, provided not all edges in F are incident with the same vertex. In this paper, we find that under similar condition, the number of faulty edges can be much greater and the same result still holds. More precisely, we show that, for up to |F|=2n-5 faulty edges, each edge of the faulty hypercube Qn-F lies on a cycle of every even length from 6 to 2n with each vertex having at least two healthy edges adjacent to it, for n≧3. Moreover, this result is optimal in the sense that the result can not be guaranteed, if there are 2n-4 faulty edges.