关于互连网络的几个猜想

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

On conjectures of interconnection networks

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.