论文研究-边故障[k]元[n]立方体的超级哈密顿交织性.pdf

[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]是最优的。