One-to-many embeddings of hypercubes into Cayley graphs generated by reversals

Among Cayley graphs on the symmetric group, some that have a noticeably low diameter relative to the degree of regularity are examples such as the "st ar" network and the "pancake" network. the latter a representative of a var iety of Cayley graphs generated by reversals. These diameter and degree con ditions make these graphs potential candidates for parallel computation net works. Thus it is natural to investigate how well they can simulate other s tandard parallel networks, in particular hypercubes. For this purpose, cons tructions have previously been given for low dilation embeddings of hypercu bes into star networks. Developing this theme further, in this paper we con struct especially low dilation maps (e.g., with dilation 1, 2, 3, or 4) of hypercubes into pancake networks and related Cayley graphs generated by rev ersals. Whereas obtaining such results by the use of "traditional" graph em beddings (i.e., one-to-one or many-to-one embeddings) is sometimes difficul t or impossible, we achieve many of these results by using a nontraditional simulation technique known as a "one-to-many" graph embedding. That is, in such embeddings we allow each vertex in the guest (i.e., domain) graph to be associated with some nonempty subset of the vertex set of the host (i.e. , range) graph., these subsets satisfying certain distance and connection r equirements which make the simulation possible.