Hyper hamiltonian laceability of Cayley graphs generated by transpositions

Abstract

Abstract Suppose that G ( V 0 ∪ 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 ∈ V i , there is a hamiltonian path in G − v between any two vertices in V 1 − 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. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 48(3), 121–124 2006