05156907

j

05156907 Laihonen, Tero Optimal $t$-edge-robust $r$-identifying codes in the king lattice. Graphs Comb. 22, No. 4, 487-496 (2006). 2006 Springer-Verlag, Tokyo EN $t$-edge-robust $r$-identifying codes king lattice optimal densities graphs

doi:10.1007/s00373-006-0682-z

{\it I. Honkala}, {\it M. G. Karpovsky} and {\it 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\ge 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$. Bal Kishan Dass (Delhi)