Some mathematical properties of cayley digraphs with applications to interconnection network design

Abstract

We consider the relationships between Cayley digraphs and their coset graphs with respect to subgroups and obtain some general results on homomorphism and broadcasting between them. We also derive a general factorization theorem on subgraphs of Cayley digraphs by their automorphism groups. We discuss the applications of these results to well-known interconnection networks such as the butterfly network, the de Bruijn network, the cube-connected cycles network and the shuffle-exchange network.

Keywords:

• Broadcasting
• Cayley digraphs
• Coset graphs
• Cross-product graphs
• Digraphs
• Graph factorization
• Homomorphism
• Interconnection networks
• Parallel processing

Acknowledgements

Wenjun Xiao’s research was supported by the Natural Science Foundation of China and Fujian Province.