Vertex-pancyclicity of twisted cubes with maximal faulty edges

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 ⁿ , even if there are up to n−2 link faults. We also show that our result is optimal.

Keywords:

• hypercubes
• twisted cubes
• fault-tolerant
• pancyclic
• vertex-pancyclic
• interconnection network

2010 AMS Subject Classifications::

• 05C45

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 ⁿ⁻² 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 ₀ choices. We can always find such a path since .

Since , we have at least 2 ⁿ⁻¹ choices. If such a path does not exist, then when n≥5, which is a contradiction.