Fault-Tolerant Edge-Pancyclicity of Möbius Cube MQ_n

摘要

As one of the most fundamental networks for parallel and distributed computation, cycle is suitable for developing simple algorithms with low communication cost. A graph G is called k-fault-tolerant edge-pancyclic if after deleting any faulty set F of k vertices and/or edges from G, every correct edge in the resulting graph lies in a cycle of every length from g to |V (G - F )|, inclusively, where g is the girth of G, the length of a shortest cycle in G. The n-dimensional Mobius cube MQn is an important variant of the hypercube Qn, which possesses some properties superior to the hypercube. This paper investigates the fault-tolerant edge-pancyclicity of MQn, and shows that if MQn(n ≥ 3) contains at most n - 3 faulty vertices and/or edges then, for any fault-free edge uv, there is a fault-free cycle of every length from 6 to |V (MQn - F )| containing the edge uv. The result is optimal in some senses.