1-Perfect Codes Over Dual-Cubes vis-à-vis Hamming Codes Over Hypercubes
Pranava K. Jha · IEEE Transactions on Information Theory · 2015
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 Qmthat is a connected (m + 1)-regular spanning subgraph of the hypercube Q2m+1, and show that it admits a 1-perfect code if and only if m = 2k- 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 Qm+1into 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.