Journal Article

The Edge-Fault-Tolerant Bipancyclicity of the Even <i>k</i>-ary <i>n</i>-cube

Jywe-Fei Fang

in The Computer Journal

Published on behalf of British Computer Society

Volume 54, issue 2, pages 255-262
Published in print February 2011 | ISSN: 0010-4620
Published online May 2010 | e-ISSN: 1460-2067 | DOI: https://dx.doi.org/10.1093/comjnl/bxq044
The Edge-Fault-Tolerant Bipancyclicity of the Even k-ary n-cube

Show Summary Details

Preview

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.

Keywords: interconnection networks; k-ary n-cubes; fault tolerance; bipancyclicity

Journal Article.  0 words. 

Subjects: Computer Science

Full text: subscription required

How to subscribe Recommend to my Librarian

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.