Perfect distance-dominating set conjecture for integer grids

Let Λn\Lambda_n be the integer grid with vertex set ZnZ^n, with adjacency given by Lee distance 11. Let PkP_k be the path on kk vertices, and let an rr-PDDS[Pk][P_k] mean an rr-perfect distance-dominating set whose components are isomorphic to PkP_k.

Perfect distance-dominating set conjecture. For k1k\geq 1, there is no rr-PDDS[Pk][P_k] in Λn\Lambda_n for n3n\geq 3 and r>1r>1, with the exception of a 22-PDDS[P2][P_2] in Λ3\Lambda_3.

This conjecture simultaneously extends the Golomb–Welch and diameter-perfect Lee-code questions. The stated exception corresponds to the known DPL(3,6)DPL(3,6) construction, while the remaining nonexistence claims are open.

Sources & referencesView supporting material

Primary source

Peter Horak and Bader F. AlBdaiwi, “Diameter Perfect Lee Codes”, arXiv:1109.3475 (2012).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.