完全对换网络的一簇猜想  

One Variety Conjectures of Complete-transposition Network

作　　者：师海忠[1] 王国亮[1] 马继勇[1] 侯斐斐[1] 

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

出　　处：《计算机科学》2012年第B06期404-407,共4页Computer Science

基　　金：甘肃省自然科学基金(ZS991-A25-017-G)资助

摘　　要：完全对换网络是互连网络设计中的一个重要的Cayley图模型,关于完全对换网络的一簇猜想如下:对任意整数n≥3,当n=0(mod 4)或1(mod 4)时,完全对换网络CTn是k(1≤k≤n(n-1)4)个边不交的哈密尔顿圈和(n(n-1)2-2k)个完美对集的并;当n=2(mod 4)或3(mod 4)时,完全对换网络CTn是k(1≤k≤n(n-1)-24)个边不交的哈密尔顿圈和(n(n-1)2-2k)个完美对集的并。证明了当n=3,4和n=5(1≤k≤4),n=6(1≤k≤6)时,这簇猜想是正确的。Complete-transposition Networks are important cayley graphs model in networks design.One variety conjectures of complete-transposition networks were proposed as follows：for any intger n≥3,if n=0（mod 4） or 1（mod 4）,CTn is a union of k（1≤k≤n（n-1） 4） edge-disjoint Hamiltonian cycles and n（n-1） 2-2k perfect matchings.if n=2（mod 4） or 3（mod 4）,CTn is a union of k（1≤k≤n（n-1）-2 4） edge-disjoint Hamiltonian cycles and n（n-1） 2-2k perfect matchings.We proved the conjectures are true for n=3,4,and n=5（1≤k≤4）,n=6（1≤k≤6）.

关 键 词：互连网络 CAYLEY图 完全对换网络 哈密尔顿圈 完美对集 

分 类 号：TP393[自动化与计算机技术—计算机应用技术]