A new family of Cayley graph interconnection networks based on wreath product and its topological properties

This paper introduces a new type of Cayley graphs for building large-scale interconnection networks, namely WG_n^2m\mathit{WG}_{n}^{2m}, whose vertex degree is m+3 when n≥3 and is m+2 when n=2. A routing algorithm for the proposed graph is also presented, and the upper bound of the diameter is deduced as ⌊5n/2⌋. Moreover, the embedding properties and maximal fault tolerance are also analyzed. Finally, we compare the proposed networks with some other similar network topologies. It is found that WG_n^2m\mathit{WG}_{n}^{2m} is superior to other interconnection networks because it helps to construct large-scale networks with lower cost.