New Bounds for Codes Identifying Vertices in Graphs

Let $G=(V,E)$ be an undirected graph. Let C be a subset of vertices that we shall call a code. For any vertex v∈ V, the neighbouring set $N(v,C)$ is the set of vertices of C at distance at most one from v. We say that the code C identifies the vertices of G if the neighbouring sets N(v,C), v∈ V, are all nonempty and different. What is the smallest size of an identifying code C ? We focus on the case when G is the two-dimensional square lattice and improve previous upper and lower bounds on the minimum size of such a code.