An almost complete description of perfect codes in direct products of cycles (Q864867): Difference between revisions

The concept of perfect codes can be generalized to graphs in the obvious manner: an \(r\)-perfect code in a graph \(G\) is a set of vertices \(C \subseteq V(G)\) with the property that for any vertex \(v \in V(G)\), \(d(v,c) \leq r\) for exactly one vertex \(c \in C\). Two vertices \((v_1,v_2)\) and \((w_1,w_2)\) in the direct product of two graphs, \(G\) and \(H\), are adjacent whenever \(v_1w_1 \in E(G)\) and \(v_2w_2 \in E(H)\). The authors study perfect codes in the direct product of \(n \geq 2\) cycles, give a sufficient condition for the existence of such codes -- that the length of each cycle in the product is a multiple of \(r^n + (r+1)^n\) -- and finally conjecture that for \(r \geq 2\) the sufficient condition is also necessary (which is proved for \(n \leq 4\) and cycles of length at least \(2r+2\)).