Graph Decompositions into Generalized Cubes

Abstract

For a positive integer $d$, the usual $d$-dimensional cube $Q_d$ is defined to be the graph $(K_2{)}^d$, the Cartesian product of $d$ copies of $K_2$. We define the generalized cube $Q_{d,k}$ to be the graph $(K_k{)}^d$ for positive integers $d$ and $k$. We investigate the decompositions of the complete graph $K_{k^d}$ and the complete $k$-partite graph $K_{k\times k^{d-1}}$ into generalized cubes when $k$ is the power of a prime and $d$ is any positive integer, and some generalizations. We also use these results to show that $Q_5$ divides $K_{96}$.