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

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