Hyper hamiltonian laceability of Cayley graphs generated by transpositions

Suppose that G(V-0 boolean OR V-1, E) is a bipartite graph with partite sets of equal size. G is called hyper hamiltonian laceable if (1) it has a hamiltonian path between any pair of vertices in different partite sets, and (2) for any vertex V is an element of V-i, there is a hamiltonian path in G - v between any two vertices in V1-i. Star and bubble-sort graphs have been considered as interconnection networks for parallel and distributed systems, and these graphs are known to be hyper hamiltonian laceable. Furthermore, it is well known that these graphs belong to the class of Cayley graphs on symmetric groups generated by a set of transpositions. In this article, we generalize those results by showing that any Cayley graph generated by transpositions is hyper hamiltonian laceable. (C) 2006 Wiley Periodicals, Inc.