Cycle Embedding on the M¨obius Cube with Both Faulty Nodes and Faulty Edges
Sun‐Yuan Hsieh, Nai-Wen Chang · 2006
A graph G = (V,E) is said to be pancyclic if it contains fault-free cycles of all lengths from 4 to |V | in G. Let Fv and Fe be the sets of faulty nodes and faulty edges of an n-dimensional M¨obius cube MQn, respectively, and let F = Fv U Fe. In this paper, we show that MQn - F contains a fault-free Hamiltonian path when |F| \le n - 1 and n \ge 1. We also show that MQn - F is pancyclic when |F| \le n - 2 and n \ge 2. Since MQn is regular of degree n, both results are optimal in the worst case.