Previous | [ 1] | [ 2] | [ 3] | [ 4] | [ 5] | [ 6] | [ 7] | [ 8] | [ 9] | [ 10] | [ 11] |

¡@

QIANG DONG^{+}

*
Web Sciences Center
School of Computer Science and Engineering
University of Electronic Science and Technology of China
Chengdu, 611731 P.R. China
*

The *k*-ary n-cube is one of the most popular interconnection networks for parallel
computing. This paper addresses the size of a largest connected component of a faulty
*k*-ary *n*-cube. We prove that, in a *k*-ary *n*-cube (*k* >= 4 and *n* >= 2) with up to 4*n*¡V2 faulty
vertices, all fault-free vertices but at most two constitute a connected component. Moreover,
this assertion holds if and only if the set of all faulty vertices is equal to the
neighborhood of a pair of fault-free adjacent vertices.

*
Keywords:
*
interconnection networks,

Retrieve PDF document (**201307_11.pdf**)

Received March 31, 2011; accepted July 25, 2011.

Communicated by Chia-Feng Juang.
^{*} This work was supported by National Nature Science Foundation of China (No. 61003231, No. 61103109),
Research Fund for the Doctoral Program of Higher Education of China (No. 20120185120017), China Postdoctoral
Science Foundation (No. 2013M531951), and Fundamental Research Funds for the Central Universities
(No. ZYGX2011J057, No. ZYGX2012J071, No. ZYGX2012J085).
^{+} Corresponding author: Qiang Dong (dongq@uestc.edu.cn).