The Minimum Density of an Identifying Code in the King LatticeDiscrete Mathematics, Vol. 276(1/3), pp. 95-109, 2004.
Irène CHARON (*), Iiro HONKALA (#), Olivier HUDRY (*), Antoine LOBSTEIN (*)
(*) Centre National de la Recherche Scientifique
Ecole Nationale Supérieure des Télécommunications
46 rue Barrault, 75634 Paris cédex 13, France
{charon, hudry, lobstein}@infres.enst.fr
(#) Department of Mathematics
University of Turku, 20014 Turku, Finland
honkala@utu.fi
Abstract. Consider a connected undirected graph G=(V, E) and a subset of vertices C. If for all vertices v in V, the sets Br (v) $\cap$ 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 2-dimensional square lattice with two diagonals.