CAJ | 학술논문

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립방체（기위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시최우적。
The k-aryn-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 k4 and n2 , 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.