BSCC(4,k)的Hamilton圈分解  

Hamilton Descomposition of BSCC(4,k)

作　　者：胡艳红[1] 师海忠[1] 

机构地区：[1]西北师范大学数学与统计学院,兰州730070

出　　处：《计算机科学》2016年第S1期73-76,共4页Computer Science

摘　　要：冒泡排序连通圈网络BSCC(n)是一类重要的互连网络。2010年师海忠提出了如下猜想:冒泡排序连通圈网络BSCC(n)(n≥4)可分解为边不交的Hamilton圈和完美对集的并。记BSCC(n)为BSCC(n,0),对BSCC(n,0)的每个顶点用一个三角形代替,得到新网络BSCC(n,1),对BSCC(n,1)的每个顶点用三角形代替得到BSCC(n,2),类似迭代k次得新网络BSCC(n,k)。师海忠进一步提出猜想2:BSCC(n,k)可分解为边不交的一个Hamilton圈和一个完美对集的并。证明了BSCC(4,k)可分解成边不交的一个Hamilton圈和一个完美对集的并。Bubble-sort connected cycle is an important class of interconnection network.Shi Hai-zhong conjectured that BSCC(n)(n≥4)is a union of edge disjoint a Hamiltonian cycle and a perfect matching.Denoting BSCC(n)as BSCC(n,0),we studied the new network BSCC(4,1)by using a triangle to replace per vertex of BSCC(4,0),and BSCC(4,2)was gotten by using a triangle to replace every vertex of BSCC(4,1).In the similar way,the new network was gotten by using a triangle to replace every vertex for ktimes.Shi Hai-zhong raised the conjecture 2further more:BSCC(n,k)is a union of edge disjoint a Hamiltonian cycle and a perfect matching.In this paper,we proved that BSCC(4,k)is a union of edge disjoint a Hamiltonian cycle and a perfect matching.

关 键 词：冒泡排序连通圈网络 HAMILTON圈 猜想 完美对集 CAYLEY图 

分 类 号：TP338.6[自动化与计算机技术—计算机系统结构]