On identifying codes in the King grid that are robust against edge deletions (Q1010708): Difference between revisions

Summary: 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 \({\mathbb Z}^2\) where two different vertices are adjacent if their Euclidean distance is at most \(\sqrt{2}\).