1-Perfect Codes Over Dual-Cubes vis-a-vis Hamming Codes Over Hypercubes

A 1-perfect code of a graph G is a set C subset of V(G) such that the 1-balls centered at the vertices in C constitute a partition of V(G). In this paper, we consider the dual-cube DQ(m) that is a connected (m+1)-regular spanning subgraph of the hypercube Q(2m+1), and show that it admits a 1-perfect code if and only if m = 2(k) - 2, k >= 2. The result closely parallels the existence of Hamming codes over the hypercube. The algorithm for that purpose employs a scheme by Jha and Slutzki for a vertex partition of Q(m+1) into Hamming codes using a Latin square, and carefully allocates those codes among various m-cubes in DQ(m). The result leads to tight bounds on domination numbers of the dual-cube and the exchanged hypercube.