On codes identifying vertices in the two-dimensional square lattice with diagonals

Fault diagnosis of multiprocessor systems motivates the following graph-theoretic definition. A subset C of points in an undirected graph G=(V, E) is called an identifying code if the sets B(v)/spl cap/C consisting of all elements of C within distance one from the vertex v are different. We also require that the sets B(v)/spl cap/C are all nonempty. We take G to be the infinite square lattice with diagonals and show that the density of the smallest identifying code is at least 2/9 and at most 4/17.