Abstract: The [k-ary] [n]-cube [Qkn] is one of the most popular interconnection networks in large-scale multiprocessor systems. For [1mn-1], let [F] be a faulty set in [Qkn] consisting of a nonempty node set [VF] and a nonempty link set [EF] such that there does not exist a [Qkn-m] in [Qkn-F] and the set of [Qkn-m]’s damaged by [VF] and the set of [Qkn-m]??s damaged by [EF] do not contain each other. Let [f*(n,m)] be the minimum cardinality of the faulty set [F] required to damage all the [Qkn-m]’s in[Qkn]. In this paper, the following results are proved. For odd [k3], [f*(n,1)] is [k+1] and [f*(n,n-1)] is [kn-1-1+n]. The lower and upper bounds on [f*(n,m)] are [km] and [Cm-1n-1km+Cm-1n-2km-1], respectively. Finally, the example shows that the upper bound [Cm-1n-1km+Cm-1n-2km-1] is optimal.

Key words: reliability, interconnection networks, [k-ary] [n-cubes], faulty sets

摘要： [k]元[n]方体[Qkn]是设计大规模多处理机系统时最常用的互连网络拓扑结构之一。对于[1mn-1]，设[F]是[Qkn]中的一个由非空点集[VF]和非空边集[EF]构成的故障集，满足[Qkn-F]中不存在[Qkn-m]且[VF]破坏的[Qkn-m]的集合与[EF]破坏的[Qkn-m]的集合互不包含。设[f*(n,m)]是破坏[Qkn]中的所有子立方[Qkn-m]所需要的故障集[F]的最小基数。证明了对于奇数[k3]，[f*(n,1)]为[k+1]，[f*(n,n-1)]为[kn-1-1+n]，[f*(n,m)]的上下界分别为[Cm-1n-1km+Cm-1n-2km-1]和[km]。举例说明了上界[Cm-1n-1km+Cm-1n-2km-1]是最优的。

关键词: 可靠性, 互连网络, [k]元[n]方体, 故障集