Perfect distance-dominating set conjecture for integer grids

About 15 years old · traced to

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 k≥1k\geq 1, there is no rr-PDDS[Pk][P_k] in Λn\Lambda_n for n≥3n\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.

References

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.