Optimal \(t\)-edge-robust \(r\)-identifying codes in the king lattice (Q882790)

\textit{I. Honkala}, \textit{M. G. Karpovsky} and \textit{L. B. Levitin} [IEEE Trans. Inf. Theory 52, No. 2, 599--612 (2006)] introduced the concept of a \(t\)-edge-robust \(r\)-identifying code. This paper considers these codes in the king lattice and presents several optimal densities. In particular, the optimal densities for \(t\)-edge-robust \(1\)-identifying codes \((t\geq 1)\) in the king lattice have been presented. This result improves on the construction given by Honkala, Karpovsky and Levitin in which a \(1\)-edge-robust \(1\)-identifying code in the king lattice of density \(3/8\) was given. The code considered in the paper yields the density \(1/3\) which is optimal. It is also observed that while the density of a \(1\)-edge-robust \(r\)-identifying code can be made arbitrarily small by chosing \(r\) large enough, the density of a \(3\)-edge-robust \(r\)-identifying code is never less than \(1/2\).