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



: Honkala I, Laihonen T

Publisher: ELECTRONIC JOURNAL OF COMBINATORICS

: 2008

: The Electronic Journal of Combinatorics

: ELECTRONIC JOURNAL OF COMBINATORICS

: ELECTRON J COMB

: 15

: 1

: 13

: 1077-8926


Assume that G = (V,E) is an undirected graph, C subset of V. For every v is an element of V we denote I-r (G;v) = {u is an element of 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 is an element of 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 form 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 root 2.



Last updated on 2024-26-11 at 11:13