New classes of interconnection topology structures and their properties
Hong Zhu, Zheng Sun · Wuhan University Journal of Natural Sciences · 1996
In the first part of this paper, three generalizations of arrangement graphA n,k of [1], namelyB n, k,C n, k andD n, k, are introduced. We prove that all the three classes of graphs are vertex symmetric, two of them are edge symmetric. They have great faulty tolerance and high connectivity. We give the diameters ofB n, kandC n,k, the Hamiltonian cycle ofC n, k and Hamiltonian path ofB n,k. We list several open problems, one of them related to the complexity of sorting algorithm on the arrangement graphs. All these graphs can be thought as generalizations of star graph but are more flexible so that they can be considered as new interconnection network topologies. In the second part of this paper, we provide other four classes of combinatorial graphes,Ch n, Cyn, Zhn, andZy n. Many good properties of them, such as high node-connectivity, node symmetry, edge symmetry, diameter, ets., are shown in this paper.