计算机工程与应用 ›› 2014, Vol. 50 ›› Issue (21): 39-43.

• 理论研究、研发设计 • 上一篇    下一篇

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

张淑蓉,王世英,董  操   

  1. 山西大学 数学科学学院,太原 030006
  • 出版日期:2014-11-01 发布日期:2014-10-28

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

ZHANG Shurong, WANG Shiying, DONG Cao   

  1. School of Mathematical Sciences, Shanxi University, Taiyuan 030006, China
  • Online:2014-11-01 Published:2014-10-28

摘要: [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]立方体

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