The minimum density of an identifying code in the king lattice. (Q1422415)

Let \(G=(V,E)\) be a connected undirected graph and \(C\subseteq V\). If for all vertices \(v\in V\), the sets \(B_{r}(v)\cap C\) are nonempty and different, where \(B_{r}(v)\) denotes the set of vertices within distance \(r\) from \(v\), then \(C\) is called an \(r\)-identifying code in \(G\). In this paper the graph \(G\) is the infinite two-dimensional square lattice with two diagonals (the king lattice). If \(Q_{n}\) denotes the set of vertices \((x,y)\in \mathbb{Z}\times \mathbb{Z}\) with \(| x| \leq n\) and \(| y| \leq n\), the density of a code \(C\) is defined as \(D(C)=\limsup _{n\rightarrow \infty}| C\cap Q_{n}| /| Q_{n}| \). For a given integer \(r\), the minimum density of an \(r\)-identifying code is denoted by \(D(r)\). In this paper it is shown that \(D(r)=1/4r\) for all \(r\geq 2\). Note that it is known that \(D(1)=1/4.5\).