计算机科学 ›› 2015, Vol. 42 ›› Issue (Z11): 245-246.

• 网络与通信 • 上一篇    下一篇

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

师海忠,师越   

  1. 西北师范大学数学与统计学院 兰州730070,图科技大数据研究中心 兰州730070
  • 出版日期:2018-11-14 发布日期:2018-11-14

Variety of Conjectures on Group-theoretic Model for Interconnection Networks

SHI Hai-zhong and SHI Yue   

  • Online:2018-11-14 Published:2018-11-14

摘要: 连通图生成的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图,对换图,Hamilton图,完美对集,猜想

Abstract: 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 m=2r,then the Cayley graph generated by G is the union of k(0≤k≤r) edge-disjoint Hamiltonian cycles and m-2k 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.

Key words: Cayley graph,Transposition graph,Hamiltonian cycle,Perfect mathching,Conjecture

[1] Aker S B,Krishnamurthy B.A group-theoretic model for interconnection networks[J].IEEE Transactions on Computers,1989,38(4):555-565
[2] Lakshimivarahan S,Jwo J S,Dhall S.Symmetric interconnection networks based on Cayley graph of permutation groups:A survey[J].Parallel Computing,1993,19(4):361-407
[3] 师海忠.互连网络的代数环模型[D].北京:中国科学院应用数学研究所,1998
[4] 师海忠,路建波.关于互连网络的几个猜想[J].计算机工程与应用,2008,4(31):112-115
[5] Shi H Z,Niu P F,Lu J B.One conjecture of bubble sort graphs[J].Information Processing Letters,2011,111(18):926-929
[6] 师海忠,马继勇,牛攀峰,等.关于修正冒泡排序网络的一簇猜想猜想[J].计算机科学,2011,8(10A):265-267,5
[7] 师海忠,王国亮,马继勇,等.完全对换网络的一簇猜想[J].计算机科学,2012,9(6A):404-407
[8] 师海忠,侯菲菲,马继勇,等.关于轮网络的一簇猜想[J].数学的实践与认识,2013,3(10):139-144
[9] 路建波,师海忠.Star网络S5的Hamilton 圈分解[J].数学的实践与认识,2010,0(31):193-197
[10] 路建波,师海忠,牛攀峰.Star网络S6 的Hamilton 圈分解[J].工程数学学报,2011,8(4):565-568
[11] Hussak W,Schroder H.A Hamiltonian decomposition of 5-star[J].International Journal of Computer and Information Engineering,2010,4(1):39-43
[12] Cada R,Kaiser T,Rosenfeld M,et al.Disjoint Hamilton cycles in the star graph[J].Information Processing Letters,2009,110(1):30-35
[13] Bondy J A,Murty U S R.Graph Theory[M].Springer,2008
[14] Huang R-W.The property of edge-disjoint Hamiltonian cycles in transposition networks and hypercube-like networks[J].Discrete Applied Mathematics,2015,118(1):109-122

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!