On identifying codes in the King grid that are robust against edge deletions

Iiro Honkala ; Tero Laihonen

The electronic journal of combinatorics, Tome 15 (2008)

Résumé

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}$.

Détail

DOI : 10.37236/727

Classification : 05C69, 05C12, 05C38, 05C90, 94B05, 94C12, 94B65
Mots-clés : identifying code, edge deletion, king grid, optimal code, code robust against edge deletion