The Edge-Fault-Tolerant Bipancyclicity of the Even k-ary n-cube
J.-F. Fang · The Computer Journal · 2010
The interconnection network considered in this paper is the k-ary n-cube that is an attractive variance of the well-known hypercube. Many interconnection networks, including the ring, torus and hypercube, that are attractive in both theoretical interests and practical systems can be regarded as the subclasses of the k-ary n-cubes. Stewart and Xiang have investigated the fault-tolerant path embedding properties of the k-ary n-cube [2008, IEEE Trans. Parallel Distrib. Syst., 19 1071–1085]. From their results, we know that the k-ary n-cube is a (2n – 2)-edge-fault-tolerant Hamiltonian for k even. In this paper, we do a further investigation for the fault-tolerant cycle embedding properties of the k-ary n-cubes. First, we introduce a new graph called the ladder-wounded cycle-of-ladders (LWCOL). By embedding the LWCOL into the k-ary n-cubes for k even with at most 2n – 2 edge faults, we show that the k-ary n-cube is (2n – 2)-edge-fault-tolerant bipancyclic for k even; that is, it embeds all cycles of even lengths ranging from 4 to N when there exist at most 2n – 2 edge faults, where N is the order of the network. Since the degree of the k-ary n-cube is 2n, the result is optimal.