Optimal \(t\)-edge-robust \(r\)-identifying codes in the king lattice
type: Item
instance of: scholarly article
title: Optimal \(t\)-edge-robust \(r\)-identifying codes in the king lattice
zbMATH Open document ID: 1124.94013
author: Tero Laihonen
published in: Graphs and Combinatorics
publication date: 2007-05-24T00:00:00Z
review text: \textit{I. Honkala}, \textit{M. G. Karpovsky} and \textit{L. B. Levitin} [IEEE Trans. Inf. Theory 52, No. 2, 599--612 (2006)] introduced the concept of a \(t\)-edge-robust \(r\)-identifying code. This paper considers these codes in the king lattice and presents several optimal densities. In particular, the optimal densities for \(t\)-edge-robust \(1\)-identifying codes \((t\geq 1)\) in the king lattice have been presented. This result improves on the construction given by Honkala, Karpovsky and Levitin in which a \(1\)-edge-robust \(1\)-identifying code in the king lattice of density \(3/8\) was given. The code considered in the paper yields the density \(1/3\) which is optimal. It is also observed that while the density of a \(1\)-edge-robust \(r\)-identifying code can be made arbitrarily small by chosing \(r\) large enough, the density of a \(3\)-edge-robust \(r\)-identifying code is never less than \(1/2\).
Mathematics Subject Classification ID: 94B25
Mathematics Subject Classification ID: 05C90
zbMATH DE Number: 5156907
zbMATH Keywords: \(t\)-edge-robust \(r\)-identifying codes
zbMATH Keywords: king lattice
zbMATH Keywords: optimal densities
zbMATH Keywords: graphs
reviewed by: Bai Kishan Dass
MaRDI profile type: Publication
full work available at URL: s00373-006-0682-z
OpenAlex ID: W2027213710
cites work: Bounds on identifying codes
cites work: General bounds for identifying codes in some infinite regular graphs
cites work: The minimum density of an identifying code in the king lattice.
cites work: Identifying codes with small radius in some infinite regular graphs
cites work: Bounds for codes identifying vertices in the hexagonal grid
cites work: On codes identifying vertices in the two-dimensional square lattice with diagonals
cites work: An optimal edge-robust identifying code in the triangular lattice
cites work: On robust and dynamic identifying codes
cites work: On the identification of sets of points in the square lattice
cites work: On a new class of identifying codes in graphs
cites work: On a new class of codes for identifying vertices in graphs
cites work: Sequences of optimal identifying codes
DOI: 10.1007/S00373-006-0682-Z
description: scientific article; zbMATH DE number 5156907