On Identifying Codes in the King Grid that are Robust Against Edge Deletions - Honkala, Iiro; Laihonen, Tero (The Electronic Journal of Combinatorics, 2008)
Assume that G = (V, E) is an undirected graph, and C V. For every v V, we denote I_r(G;v) = { u C: d(u,v) ≤ 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 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 Z^2 where two different vertices are adjacent if their Euclidean distance is at most 2.