\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Iiro Honkala and Tero Laihonen}
%
%
\medskip
\noindent
%
%
{\bf On Identifying Codes in the King Grid that are Robust Against Edge Deletions}
%
%
\vskip 5mm
\noindent
%
%
%
%
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}$.



\bye