On the density of identifying codes in the square lattice

摘要

Let G = (V, E) be an undirected graph and C a subset of vertices. If the sets B-r(nu) boolean AND C, nu is an element of V, are all nonempty and different, where B-r(nu) denotes the set of all points within distance r from nu, we call C an r-identifying code. We give bounds on the best possible density of r-identifying codes in the two-dimensional square lattice. (C) 2002 Elsevier Science (USA). [References: 14]