New Bounds for Codes Identifying Vertices in Graphs

Abstract

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\in 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\in 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.