### Abstract:

The set of codewords for a standard error-correcting code can be viewed
as subset of the vertices of a hypercube. Two vertices are adjacent in a hypercube exactly when their Hamming distance is 1. A code is a perfect-error-correcting code if no two codewords are adjacent and every non-codeword is adjacent to exactly one codeword. Since such a code can be described using only vertices and adjacency, the de finition applies to general graphs rather than only to hypercubes. How does one decide if a graph can support a perfect 1-error-correcting code? The obvious way to show that such a code exists is to display the code. On the other hand, it seems difficult to show that a graph does not support such a code. We show that this intuition is correct by showing that to determine if a graph has a perfect 1-error-correcting code is an NP-complete problem. The proof is by reduction from 3-SAT. To show that perfect codes in graphs is not vacuous, we give an in nite family of graphs so that each graph in the family has a perfect 1-error-correcting code. Our graphs are based on the Towers of Hanoi puzzle, so that, each vertex is a confi guration of the puzzle and two vertices are adjacent when they are one legal move apart. We give a recursive construction which determines which vertices are codewords. There is a natural correspondence between the hypercube vertices and the binary strings,
and there is a natural correspondence between Tower of Hanoi con guration
and ternary strings. Our recursive construction also speci es which ternary
strings are codewords. We characterize the codewords as the set of ternary
strings with an even number of 1's and an even number of 2's. As part of
this characterization, we show that there is essentially one perfect 1-error-correcting code for each n. There is a unique code when n is even, but the
code is only unique up to a permutation of 0, 1, and 2 when n is odd. We
show that error-correction can be accomplished by a nite state machine
which passes over the ternary string twice, and that this machine is xed
independent of the length of the string. Encoding and decoding are the mappings between integers and codewords, and vice-versa. While algorithms for
such mappings can be derived directly from the recursive construction, we
show that encoding/decoding can be carried out by multiplication/division
by 4 and error-correction. So error-correction, encoding, and decoding can
all be done in time θ(n) for code strings of length n in these codes.