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

A 1-perfect code of a graph G is a set C ⊆ 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 D Q_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 D Qm. The result leads to tight bounds on domination numbers of the dual-cube and the exchanged hypercube.