Analysis of interconnection networks based on simple Cayley coset graphs

While the concept of Cayley coset graphs has been around for a long time, it is only recently the present authors derived conditions for a Cayley coset graph to be simple - not containing self loops and multiple edges. Building on this result a whole host of Cayley coset graphs - coset star graph, coset bubblesort graph, coset modified bubblesort graph, coset complete transposition graph to mention a few, have been identified. This paper represents the first attempt to evaluate the use of Cayley coset graphs in the design of interconnection networks for parallel computers. We first derive conditions for a simple Cayley coset graph to be vertex transitive. We then present a family of Cayley coset star graphs and analyze a number of its properties. It is shown that this family is recursively scalable, contains star graphs as a subgraph, and is Hamiltonian. We derive conditions for this family to bipartite and edge transitive. Finally, a shortest path algorithm and an enumeration of node disjoint paths are given. A number of open questions are listed in the conclusion