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.

Automated summary

An exchanged hypercube is a spanning subgraph of a hypercube that retains desirable properties while reducing interconnection complexity. This paper proves that the graph is isomorphic to an induced subgraph of the hypercube of minimum size, with the minimal hypercube comprising two factors, each containing vertex-disjoint copies of the induced subgraph. The result also applies to the dual-cube, a special case of the exchanged hypercube.