On identifying codes in the King grid that are robust against edge deletions
type: Item
instance of: scholarly article
title: On identifying codes in the King grid that are robust against edge deletions
zbMATH Open document ID: 1159.05041
author: Tero Laihonen
author: Iiro Honkala
published in: The Electronic Journal of Combinatorics
publication date: 2009-04-07T00:00:00Z
full work available at URL: https://eudml.org/doc/129770
full work available at URL: v15i1r3.html
review text: 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}\).
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C90
Mathematics Subject Classification ID: 94B05
Mathematics Subject Classification ID: 94C12
Mathematics Subject Classification ID: 94B65
zbMATH DE Number: 5540908
zbMATH Keywords: identifying code
zbMATH Keywords: edge deletion
zbMATH Keywords: king grid
zbMATH Keywords: optimal code
zbMATH Keywords: code robust against edge deletion
MaRDI profile type: Publication
Recommended article: Q3412137
Recommended article: Optimal \(t\)-edge-robust \(r\)-identifying codes in the king lattice
Recommended article: An improved lower bound for \((1,\leq 2)\)-identifying codes in the king grid
Recommended article: On identifying codes that are robust against edge changes
Recommended article: Minimum density of identifying codes of king grids
Recommended article: New bounds for (\(r, \leq 2\))-identifying codes in the infinite king grid
Recommended article: Q3101008
Recommended article: Optimal identifying codes in the infinite 3-dimensional king grid
Recommended article: On \((r,\leq 2)\)-locating-dominating codes in the infinite King grid
description: scientific article; zbMATH DE number 5540908