1-Perfect Codes Over the Quad-Cube
Pranava K. Jha · IEEE Transactions on Information Theory · 2022
A vertex subset$S$of a graph$G$constitutes a 1-perfect code if the one-balls centered at the nodes in$S$effect a vertex partition of$G$. This paper considers the quad-cube$CQ_{m}$that is a connected$(m+2)$-regular spanning subgraph of the hypercube$Q_{4m+2}$, and shows that$CQ_{m}$admits a vertex partition into 1-perfect codes iff$m=2^{k}-3$, where$k\ge 2$. The scheme for that purpose makes use of a procedure by Jha and Slutzki that constructs Hamming codes using a Latin square. The result closely parallels the existence of a 1-perfect code over the dual-cube, which is another derivative of the hypercube.