Previous [1] [2] [3] [4] [5] [6] [7] [8]

Journal of Inforamtion Science and Engineering, Vol.12 No.4, pp.603-617 (December 1996)
Properties of Star Graph, Bubble-sort Graph,
Prefix-reversal Graph and Complete-transposition Graph

Jung-Sing Jwo
Department of Computer and Information Sciences
Tunghai University
Taichung, Taiwan 407, R.O.C.

In this paper, we analyze the properties of the Cayley graphs that are related to the star graph, including the prefix-reversal (also called pancake) graph, bubble-sort graph and complete-transposition graph. Algorithms for Hamiltonian cycles, multi-dimensional grid embeddings, and the embeddings of these graphs and the star graph are proposed. It is shown that all these three graphs are Hamiltonian. An n (n - 1) ......3 2 (n - 1) dimensional grid can be embedded into a prefix-reversal graph, bubble-sort graph and complete-transposition graph with dilation six, 2n-3 and one, respectively, and all with unit expansion where n is the dimension of the graph. For the embeddings among these graphs and the star graph, the prefix reversal graph shows its superiority since all the others can be embedded into it with unit expansion and constant dilation.

Keywords: Cayley graphs, interconnection networks, multiprocessor systems, hypercubes, star graphs, bubble-sort graphs, prefix-reversal graphs, complete-transposition graphs

Received October 30, 1995; revised February 26, 1996.
Communicated by Jhing-Fa Wang.