Optimal embeddings of the exchanged hypercube and the dual-cube as vertex-induced subgraphs of the hypercube

An exchanged hypercube is a spanning subgraph of a hypercube. It retains a large num-ber of desirable properties of the hypercube, yet maintains a reduced interconnection complexity. This paper shows that the graph is isomorphic to an induced subgraph of the hypercube of the least possible size. Further, the minimal hypercube consists of two factors, each of which comprises as many vertex-disjoint copies of the induced subgraph. The result is seamlessly inherited by the dual-cube that is known to be a special case of the exchanged hypercube.& COPY; 2023 Published by Elsevier B.V.