1-Perfect Codes Over the Quad-Cube.

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. [ABSTRACT FROM AUTHOR]