低维修正冒泡排序网络一个猜想的证明

Proving of a Conjecture of Low Dimension Modified Bubble Sort Network

修正冒泡排序网络是互连网络设计中的一个重要的Cayley图模型,关于修正冒泡排序网络的一个猜想如下:对于任意的自然数n≥3,如果n为奇数,则修正冒泡排序网络Yn是n-1/2个边不交的哈密尔顿圈以及一个完美对集的并;如果n为偶数,则修正冒泡排序网络Yn是n/2个边不交的哈密尔顿圈的并.证明了当n=3,4,5时,这个猜想是正确的.

Modified bubble sort networks are important networks designed from Cayley graph model. One conjecture is proposed as follows： For any integer n≥3,if n is odd, the modified bubble sort network Y. is a union of n-1/2 edge-disjoint Hamiltonian cycles and a perfect matching of Y. ~ if n is even,the modified bub 7/ ble sort network Yn is a union of n/2 edge-disjoint Hamiltonian cycles. It is proved that the conjecture is true for n=3,4,5.