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

摘要

A 1-perfect code of a graph is a set such that the 1-balls centered at the vertices in constitute a partition of . In this paper, we consider the dual-cube that is a connected -regular spanning subgraph of the hypercube , and show that it admits a 1-perfect code if and only if , . 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 into Hamming codes using a Latin square, and carefully allocates those codes among various -cubes in . The result leads to tight bounds on domination numbers of the dual-cube and the exchanged hypercube.