计算机工程与应用 ›› 2006, Vol. 42 ›› Issue (24): 24-.

• 博士论坛 • 上一篇    

交叉立方体环的Hamilton连通性和Pancyclicity性

喻昕,吴敏,王国军   

  1. 中南大学信息科学与工程学院
  • 收稿日期:2006-06-23 修回日期:1900-01-01 出版日期:2006-08-21 发布日期:2006-08-21
  • 通讯作者: 喻昕 yuxin21

Hamilton-connectivity and Pancyclicity of Crossed Cube-connected Ring

Xin Yu,,   

  1. 中南大学信息科学与工程学院
  • Received:2006-06-23 Revised:1900-01-01 Online:2006-08-21 Published:2006-08-21
  • Contact: Xin Yu

摘要: 交叉立方体是超立方体互连网络的一种变型,它的某些性质优于超立方体。例如,其直径几乎是超立方体的一半;当n≥3,交叉立方体CQn具有Hamilton连通性;当n≥2,所有长度在4 到2n 之间的圈都能够以扩张1嵌入CQn,即交叉立方体具有Pancyclity性。但是,交叉立方体同超立方体一样,当需要升级时,必须成倍增加结点。交叉立方体环互连网络CRN作为层次环互连网络HRN[8]的一种,可以有效地克服这个缺点,当需要升级时,只需在环上增加一个交叉立方体。在本文中,证明了交叉立方体环互连网络仍然保持了交叉立方体具有的Hamilton连通性和Pancyclity性。↑♂

关键词: Hamilton连通性, pancyclicity性, 交叉立方体环, 交叉立方体, 超立方体

Abstract: Crossed cube is a variation of hypercube, but some properties of the former are superior to those of the latter. For example, the diameter of crossed cube is approximately half that of the hyper cube; if n≥3, the crossed cube CQn is Hamilton-connected; if n≥2, any circle of length l(4≤ l ≤2n )can be embedded into the crossed cube CQn with dilation 1, that is pancyclicity of crossed cube. However, it is necessary to double the number of nodes to upgrade crossed cube like hypercube. As a kind of hierarchical ring interconnection networks HRN, crossed cube-connected ring interconnection network CRN can effectively overcome the disadvantage. When upgraded, it only need to be added a crossed cube. In this paper, we prove that CRN still maintains the Hamilton –connectivity and pancyclicity of crossed cube.

Key words: Hamilton-connectivity, pancyclicity, crossed cube-connected ring, crossed cube, hypercube