Optimal embeddings of the exchanged hypercube and the dual-cube as vertex-induced subgraphs of the hypercube
Pranava K. Jha · Discrete Applied Mathematics · 2023
An exchanged hypercube is a spanning subgraph of a hypercube. It retains a large number 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.