In the first part of this- paper, three generalizations of arrangement graph A.,k of [1], namely Bn,k, Cn,k and Dn,k , are introduced. We prove that all the three classes of graphs are vertex symmetric, two of them ar...In the first part of this- paper, three generalizations of arrangement graph A.,k of [1], namely Bn,k, Cn,k and Dn,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 of B..k and Cn,k, the Hamiltonian cycle of Cn,k and Hamiltonian path of B.,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, Chn , Cyn, Zhn and Zyn. Many good properties of them, such as high node--connectivity, node symmetry, edge symmetry, diameter, ets., are shown in this paper.展开更多
文摘In the first part of this- paper, three generalizations of arrangement graph A.,k of [1], namely Bn,k, Cn,k and Dn,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 of B..k and Cn,k, the Hamiltonian cycle of Cn,k and Hamiltonian path of B.,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, Chn , Cyn, Zhn and Zyn. Many good properties of them, such as high node--connectivity, node symmetry, edge symmetry, diameter, ets., are shown in this paper.
