On the fault-tolerant pancyclicity of crossed cubes
Wen‐Tzeng Huang, Woei-kae Chen, Chin‐Hsing Chen · 2003
A graph is pancyclic if it contains all cycles from lengths 4 to |V(G)|. An n-dimensional crossed cube, an important variation of hypercube denoted as CQ/sub n/, has been proved to be pancyclic because it contains all cycles whose lengths range from 4 to |V(CQ/sub n/)|. Since vertex and edge faults may occur when a network is used, it is practical and meaningful to evaluate the performance of a faulty network. Moreover the vertex fault-tolerant Hamiltonicity and the edge fault-tolerant Hamiltonicity measure the performances of the Hamiltonian properties in the faulty networks. From this fault-tolerant concept, we propose using the fault-tolerant pancyclicity of networks to measure the performance of faulty networks. In this paper we consider a faulty crossed n-cube with vertex and/or edge faults here. Let the faulty set F be a subset of V(CQ/sub n/)/spl cup/E(CQ/sub n/). We prove that any cycle of length l(4/spl les/l/spl les/|V(CQ/sub n/)|-f/sub /spl nu//) can be embedded into a faulty crossed n-cube CQ/sub n/-F with dilation 1, where |F|=f/sub /spl nu//+f/sub e/ is less than n-2, f/sub /spl nu// is the number of faulty vertices of F, f/sub e/ is the number of faulty edges of F, and n is greater than 2. The results can readily be used in the optimum embedding of a ring of the specified length in a faulty crossed cube.