Uniform emulations of Cartesian-product and Cayley graphs (Q5957297)

Simulations of interconnection networks of parallel computer systems can be modeled by mappings of graphs to other (smaller) graphs. This paper studies such mappings, called emulations, and the special forms of emulations, iso-retractions, and uniform emulations. The paper focusses on such mappings for graphs formed by Cartesian products, and subclasses of the Cayley graphs. Necessary and sufficient conditions are given for the existence of an iso-retraction of the Cartesian product of \(G\) and \(H\) onto \(G\); and the uniform emulations of the \(n\)-dimensional hypercube onto the \(n-1\)-dimensional hypercube are studied.