On the complexity of the embedding problem for hypercube related graphs (Q1801670)

An important family of graphs is the \(n\)-dimensional hypercube, the graph with \(2^ n\) nodes labelled \(0,1,\dots,2^ n-1\) and an edge joining two nodes whenever their binary representation differs in a single coordinate. The problem of deciding if a given source graph is a partial subgraph of an \(n\)-dimensional cube has recently been shown to be NP- complete. We illustrate a reduction technique used to obtain NP-completeness results for a variety of hypercube related graphs. We consider the subgraph isomorhism problem on two related families of guest graphs, the dilation two hypercubes and generalized hypercubes. We show that the embedding problem for both of these problems is NP-complete.