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.

I. Introduction

1-perfect codes constitute a significant field of study by virtue of their applications in multiprocessor systems, communication systems, and a number of other areas in the wide digital world. They have the capability to detect two or fewer errors, and correct a single error. Among various types of 1-perfect codes, the Hamming codes [4], based on the topology of the hypercubes, are the foremost. Meanwhile the problem of deciding whether or not a graph supports a 1-perfect code is NP-complete [15] even for planar 3-regular graphs.