关于互连网络群论模型的一簇猜想

Variety of Conjectures on Group-theoretic Model for Interconnection Networks

连通图生成的Cayley图是作为互连网络的群论模型提出来的概念。猜想:设G=(V,E)是具有顶点集{1,2,…,n}(n>2)和m条边的连通图。如果m=2r,则由G生成的Cayley图是边不交的k(0≤k≤r)个Hamilton图和m-2k个完美对集的并;如果m=2r+1,则由G生成的Cayley图是边不交的k(0≤k≤r)个Hamilton图和m-2k个完美对集的并。特别地,对于k=r和星网络,这个猜想的特殊情形是1998年由师海忠提出来的。

Cayley graph generated by a connected graph was proposed to design certain interconnection networks for supercomputers,on-chip interconnection and data center networks. The conjecture is that let G= （V,E） be a connected graph with node set { 1,2,..., n } （n〉2） and m edges. If rn = 2r, then the Cayley graph generated by G is the union of k （04 k≤r） edge-disjoint Hamiltonian cycles and m-21e perfect matchings. If m= 2r＋ 1, then the Cayley graph generated by G is the union of k（0≤k≤r） edge-disjoint Hamiltonian cycles and m-2k perfect matchings. In particular, for k=r and star graph,the conjecture was proposed by Hai-zhong Shi in 1998.