Optimal identifying codes in the infinite 3-dimensional king grid

A subset C⊆VC⊆V is an rr-identifying code in a graph G=(V,E)G=(V,E) if the sets Ir(v)={c∈C∣d(c,v)≤r}Ir(v)={c∈C∣d(c,v)≤r} are distinct and non-empty for all vertices v⊆Vv⊆V. Here, d(c,v)d(c,v) denotes the number of edges on any shortest path from cc to vv. We consider the infinite nn-dimensional king grid, i.e., the graph with vertex set V=ZnV=Zn and the edge set E={{x=(x1,…,xn),y=(y1,…,yn)}∣|xi−yi|≤1for  i=1,…,n,x≠y}, and give some lower bounds on the density of an rr-identifying code. In particular, we prove that for n=3n=3 and for all r≥15r≥15, the optimal density of an rr-identifying code is 18r2. The problem finding a minimum identifying code in the 3-dimensional king grid is equivalent with a minimum packing problem of cubes in the 3-dimensional lattice so that every point is covered by a distinct and non-empty subset of cubes.