边故障k元n立方体的超级哈密顿交织性  

Hyper hamiltonian laceability of k-ary n-cubes with edge faults

作　　者：张淑蓉[1] 王世英[1] 董操[1] 

机构地区：[1]山西大学数学科学学院,太原030006

出　　处：《计算机工程与应用》2014年第21期39-43,共5页Computer Engineering and Applications

基　　金：国家自然科学基金(No.61070229);教育部高等学校博士点专项基金(No.20111401110005)

摘　　要：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.

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

分 类 号：O157.5[理学—数学]