A1 Refereed original research article in a scientific journal
On identifying codes in the king grid that are robust against edge deletions
Authors: Honkala I, Laihonen T
Publisher: ELECTRONIC JOURNAL OF COMBINATORICS
Publication year: 2008
Journal: The Electronic Journal of Combinatorics
Journal name in source: ELECTRONIC JOURNAL OF COMBINATORICS
Journal acronym: ELECTRON J COMB
Volume: 15
Issue: 1
Number of pages: 13
ISSN: 1077-8926
Abstract
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.
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.
UTU Research Portal