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 includ e the star graph, bubble-sort graph, modified bubble-sort graph, compl ete-transposition graph, prefix-reversal graph, alternating-group grap h, binary and base-b (b greater-than-or-equal-to 3) hypercube, cube co nnected cycles, bisectional graph, folded hypercube and binary orthogo nal graph. In addition, we also define a variety of generalizations of the hypercube and orthogonal graphs. The types of symmetry analyzed i nclude vertex and edge transitivity, distance regularity and distance transitivity. Since these notions of symmetry depend on the shortest p aths, as a by product we also describe the shortest path routing algor ithms for these graphs. We present a number of open problems related t o the networks described in this paper.