Abstract: The [k]-ary [n]-cube, denoted by [Qkn], as one of the most efficient interconnection networks for information transportation, has been shown as an alternative to the hypercube. A [Qkn] is bipartite if and only if [k] is even. A bipartite graph [G[V0,V1]] is called hyper hamiltonian laceable if（1）it has a hamiltonian path between any pair of vertices in different parts, and（2）for any vertex[v∈Vi], there is a hamiltonian path of [G[V0,V1]-v] between any two vertices in [V1-i], where [i∈{0,1}]. Since edge faults may occur after a network is activated, it is important to solve problems in faulty networks. This paper addresses the faulty [Qkn] with even [k4] and [n2], and proves that the [Qkn] with at most [2n-3] faulty edges is hyper hamiltonian laceable. This result is optimal to the number of edge faults tolerated.

Key words: interconnection networks, hyper hamiltonian laceability, [k]-ary [n]-cubes

摘要： [k]元[n]立方体（记为[Qkn]）是优于超立方体的可进行高效信息传输的互连网络之一。[Qkn]是一个二部图当且仅当[k]为偶数。令[G[V0,V1]]是一个二部图，若（1）任意一对分别在不同部的顶点之间存在一条哈密顿路，且（2）对于任意一点[v∈Vi]，其中[i∈{0,1}]，[V1-i]中任意一对顶点可以被[G[V0,V1]-v]中的一条哈密顿路相连，则图[G[V0,V1]]被称为是超级哈密顿交织的。因为网络中的元件发生故障是不可避免的，所以研究网络的容错性就尤为重要。针对含有边故障的[Qkn]，其中[k4]是偶数且[n2]，证明了当其故障边数至多为[2n-3]时，该故障[Qkn]是超级哈密顿交织图，且故障边数目的上界[2n-3]是最优的。

关键词: 互连网络, 超级哈密顿交织性, [k]元[n]立方体