On Identifying Codes in the King Grid that are Robust Against Edge Deletions

Abstract

Assume that $G = (V, E)$ is an undirected graph, and $C \subseteq V$. For every $v \in V$, we denote $I_r(G;v) = \{ u \in C: d(u,v) \leq r\}$, where $d(u,v)$ denotes the number of edges on any shortest path from $u$ to $v$. If all the sets $I_r(G;v)$ for $v \in V$ are pairwise different, and none of them is the empty set, the code $C$ is called $r$-identifying. If $C$ is $r$-identifying in all graphs $G'$ that can be obtained from $G$ by deleting at most $t$ edges, we say that $C$ is robust against $t$ known edge deletions. Codes that are robust against $t$ unknown edge deletions form a related class. We study these two classes of codes in the king grid with the vertex set ${\Bbb Z}^2$ where two different vertices are adjacent if their Euclidean distance is at most $\sqrt{2}$.