Mobius超立方体网络的Hamilton分解

The Hamilton Decomposition of the Mobius cubes Network

互连网络是超级计算机的重要组成部分,在设计和选择一个互连网络时,Hamilton性是评估网络性能的一个重要指标,M?bius立方体作为最重要的互连网络拓扑结构之一,也具有优良的Hamilton性,师海忠提出两个猜想:猜想1:M?bius立方体网络nMQ是Hamilton可分解的;猜想2:当n=2k( k≥2)时,nMQ是边不交的i(1≤i≤k)个Hamilton圈和n-2i个完美匹配的并;当n=2k+1(k≥1)时,nMQ是边不交的i(￡i)1￡k个Hamilton圈和n-2i个完美匹配的并。当i=k时,猜想2即为猜想1。本文将对n=3,4,5时,证明猜想1和猜想2是正确的,当n=6;i=1,2时,猜想2是成立的。

Interconnection network is an important part of super computer.In the selection and design of an interconnection network topology,Hamilton is an important index to evaluate the performance of the network and M?bius cube as the most important interconnection network topology structure,but also has excellent Hamilton.Shi Haizhong proposed two conjecture: 1, M?bius cube nMQ network is Hamilton decomposable; 2 When n =2k (k≥2),nMQ is edge disjoint i(1≤i≤k) Hamilton cycle and n -2i perfect match;When n =2k +1(k ≥1),nMQ is edge disjoint i(1≤i≤k) Hamilton cycle and n -2i perfect match.The paper will prove that the conjecture 1 and conjecture 2 is right when n =3, 4,5,the conjecture 2 is established when n =6;i =1, 2.