The minimum density of an identifying code in the king lattice Original Research Article

Consider a connected undirected graph G=(V,E) and a subset of vertices C. If for all vertices v∈V, the sets Br(v)∩C are all nonempty and different, where Br(v) denotes the set of all points within distance r from v, then we call C an r-identifying code. For all r, we give the exact value of the best possible density of an r-identifying code in the king lattice, i.e., the infinite two-dimensional square lattice with two diagonals.