摘要
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 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.
出处
《计算机工程与应用》
CSCD
2014年第21期39-43,共5页
Computer Engineering and Applications
基金
国家自然科学基金(No.61070229)
教育部高等学校博士点专项基金(No.20111401110005)
关键词
互连网络
超级哈密顿交织性
k元n立方体
interconnection networks
hyper hamiltonian laceability
k-ary n-cubes
