Star网络S_5的Hamilton圈分解  

Decomposition of Star Network S_5 into Hamilton Cycles

作　　者：路建波[1] 师海忠[1] 

机构地区：[1]西北师范大学数学与信息科学学院,甘肃兰州730070

出　　处：《数学的实践与认识》2010年第4期193-197,共5页Mathematics in Practice and Theory

基　　金：国家自然科学基金(10771091)

摘　　要：最近Star网络和Pancake网络作为超立方体(并行计算机中多处理机互连的一种著名拓扑结构)的替代品而被许多作者研究.这两种网络的一个好的特点是:与超立方体相比较,它们有较小的直径和顶点度.尤其Star网络,更是受到研究人员的极大关注.在本文中:(a)我们提出了一种在这两种网络中找Hamilton圈的新方法.(b)证明了关于Star网络S_n的一个猜想在n=5时是正确的,即给出了S_5的两个边不交的Hamilton圈,且S_5是这两个Hamilton圈的并.In recent times star and pancake networks as alternatives to hypercube（for interconnecting processors on a parallel computer） has been examined by a number of researchers.An attractive feature of these two classes of graphs is that they have small diameter and degree.Star networks,especially, are interested in many researchers .In this paper： （a） We proposed a new algorithm for embedding Hamiltonian cycle in these two classes of graphs. （b） We proved that the conjecture about star networks Snis right for n = 5,namely ,we gave two edge-disjoint Hamiltonian cycles of S5 and proved that Ssis the union of these two Hamiltonian cycles .

关 键 词：CAYLEY图 HAMILTON圈 Star网络 Pancake网络 

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