Hamiltonian path embedding and pancyclicity on the Mobius cube with faulty nodes and faulty edges
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 F-v and F-e be the sets of faulty nodes and faulty edges of an n-dimensional Mobius cube MQ(n), respectively, and let F = F-v boolean OR F-e. A faulty graph is pancyclic if it contains fault-free cycles of all lengths from 4 to \V - F-v\. In this paper, we show that MQ(n) - F contains a fault-free Hamiltonian path when \F\  = 1. We also show that MQ(n) - F is pancyclic when \F\  = 2. Since MQ(n) is regular of degree n, both results are optimal in the worst case.
hamiltonian pancyclicity mobius cubes graph-theoretic interconnection networks fault-tolerant embedding