Abstract
The n-dimensional twisted cube, denoted by TQ n , a variation of the hypercube, possesses some properties superior to the hypercube. In this paper, we show that every vertex in TQ n lies on a fault-free cycle of every length from 6 to 2 n , even if there are up to n−2 link faults. We also show that our result is optimal.
2010 AMS Subject Classifications::
Acknowledgement
The author is grateful to the National Science Council of the Republic of China, Taiwan for financially supporting this research under Contract No. NSC 98-2221-E-239-013.
Notes
Since , we have 2
n−2 choices. Note that an edge in F can eliminate two choices and
. If we cannot find such an edge, then
, which is a contradiction when n≥5.
Let and
. We have
and
. Since
. We have
. Thus, we have
(since n≥5). Thus, we can always find such an edge.
Clearly, we have l
0 choices. We can always find such a path since .
Since , we have at least 2
n−1 choices. If such a path does not exist, then
when n≥5, which is a contradiction.