关于修正冒泡排序网络的一簇猜想

One Variety Conjectures of Modified Bubble Sort Network

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

Modified bubble sort networks are important cayley graphs model in networks design.One variety conjectures of modified bubble sort networks were proposed as follows：for any integer n≥3,modified bubble sort networks Yn are a union of i edge-disjoint hamiltonian cycles and n-2i perfect matchings of Yn,and 1≤i≤︱n/2︱.We proved the conjectures are true for i=1,2.