计算机工程与应用 ›› 2008, Vol. 44 ›› Issue (31): 112-115.DOI: 10.3778/j.issn.1002-8331.2008.31.032

• 网络、通信、安全 • 上一篇    下一篇

关于互连网络的几个猜想

师海忠,路建波   

  1. 西北师范大学 数学与信息科学学院,兰州 730070
  • 收稿日期:2008-05-15 修回日期:2008-07-28 出版日期:2008-11-01 发布日期:2008-11-01
  • 通讯作者: 师海忠

On conjectures of interconnection networks

SHI Hai-zhong,LU Jian-bo   

  1. College of Mathematics and Information Science,Northwest Normal University,Lanzhou 730070,China
  • Received:2008-05-15 Revised:2008-07-28 Online:2008-11-01 Published:2008-11-01
  • Contact: SHI Hai-zhong

摘要: n-立方体是著名的互连网络,星图、煎饼图和冒泡排序图是由凯莱图模型设计出来的重要的互连网络。对换树(transposition tree)的凯莱图是一类特殊的凯莱图,星图和冒泡排序图分别是对换树为星和路的凯莱图。给出了关于n-立方体、星图、煎饼图、冒泡排序图和对换树的凯莱图的各一个猜想;提出了对换图的凯莱图的概念,进而由这一概念设计出了两个互连网络——圈图和轮图,并证明冒泡排序图和星图分别可嵌入圈图和轮图。

关键词: 猜想, 对换图的凯莱图, 圈图, 轮图

Abstract: n-cubes are famous interconnection networks.Star graphs,pancake graphs and bubble sort graphs are important interconnection networks designed from Cayley graph model.Cayley graphs of transposition trees are a class of special Cayley graphs.Star graphs and bubble sort graphs are tow kinds Cayley graphs that transposition trees are star and path,respectively.One conjecture of n-cube,star graph,pancake graph,bubble sort graph and Cayley graph of transposition tree is proposed respectively;a conception-Cayley graph of transposition graph is proposed.Furthermore two new classes of networks are developed,called the cycle graphs and the wheel graphs,and the bubble sort graphs and the star graphs embedded in the cycle graphs and the wheel graphs are proved,respectively.

Key words: conjecture, Cayley graph of transposition graph, cycle graph, wheel graph