\(d\)-cube decompositions of \(K_n\setminus K_m\) (Q675883)

Necessary conditions on \(n\), \(m\) and \(d\) are given for the existence of an edge-disjoint decomposition of \(K_n\setminus K_m\) (the complete graph \(K_n\) from which the edges of a \(K_m\) subgraph have been removed) into copies of the graph of a \(d\)-dimensional cube. Sufficiency is shown when \(d=3\) and, in some cases, when \(d=2^t\). The main result of the paper is the proof that any 3-cube decompositions of \(K_m\) can be embedded into a 3-cube decomposition of \(K_n\) if and only if \(n,m\equiv 1\) or \(16\pmod{24}\) and \(m\leq n\).