REGULAR CODES IN REGULAR GRAPHS ARE DIFFICULT

We prove that the following problems are NP-complete: (1) the existence of a 1-perfect code in a planar cubic graph, (2) partitioning a cubic graph into 1-perfect codes and (3) the existence of a completely regular code in a cubic amply regular graph. All of these are questions on the existence of regular partitions of special types. We also relate 1-perfect codes in graphs to dominating sets and 2-packings. In particular, if a graph is promised to contain a 1-perfect code then its dominating number and 2-packing number can be computed in a polynomial time.