SYMMETRY IN INTERCONNECTION NETWORKS BASED ON CAYLEY-GRAPHS OF PERMUTATION-GROUPS - A SURVEY

This survey provides a comprehensive and unified analysis of symmetry in a wide variety of Cayley graphs of permutation groups. These include the star graph, bubble-sort graph, modified bubble-sort graph, complete-transposition graph, prefix-reversal graph, alternating-group graph, binary and base-b (b greater-than-or-equal-to 3) hypercube, cube connected cycles, bisectional graph, folded hypercube and binary orthogonal graph. In addition, we also define a variety of generalizations of the hypercube and orthogonal graphs. The types of symmetry analyzed include vertex and edge transitivity, distance regularity and distance transitivity. Since these notions of symmetry depend on the shortest paths, as a by product we also describe the shortest path routing algorithms for these graphs. We present a number of open problems related to the networks described in this paper.