The minimum density of an identifying code in the king lattice.
type: Item
instance of: scholarly article
title: The minimum density of an identifying code in the king lattice.
zbMATH Open document ID: 1037.05018
DOI: 10.1016/S0012-365X(03)00306-6
author: Irène Charon
author: Olivier Hudry
author: Iiro Honkala
author: Antoine Lobstein
published in: Discrete Mathematics
publication date: 2004-02-14T00:00:00Z
review text: Let \(G=(V,E)\) be a connected undirected graph and \(C\subseteq V\). If for all vertices \(v\in V\), the sets \(B_{r}(v)\cap C\) are nonempty and different, where \(B_{r}(v)\) denotes the set of vertices within distance \(r\) from \(v\), then \(C\) is called an \(r\)-identifying code in \(G\). In this paper the graph \(G\) is the infinite two-dimensional square lattice with two diagonals (the king lattice). If \(Q_{n}\) denotes the set of vertices \((x,y)\in \mathbb{Z}\times \mathbb{Z}\) with \(| x| \leq n\) and \(| y| \leq n\), the density of a code \(C\) is defined as \(D(C)=\limsup _{n\rightarrow \infty}| C\cap Q_{n}| /| Q_{n}| \). For a given integer \(r\), the minimum density of an \(r\)-identifying code is denoted by \(D(r)\). In this paper it is shown that \(D(r)=1/4r\) for all \(r\geq 2\). Note that it is known that \(D(1)=1/4.5\).
Mathematics Subject Classification ID: 05C12
Mathematics Subject Classification ID: 94B25
Mathematics Subject Classification ID: 05C90
Mathematics Subject Classification ID: 94B65
zbMATH DE Number: 2041898
zbMATH Keywords: distance
zbMATH Keywords: square lattice
reviewed by: Ioan Tomescu
MaRDI profile type: Publication
cites work: Q4948746
cites work: Bounds on identifying codes
cites work: General bounds for identifying codes in some infinite regular graphs
cites work: Identifying codes with small radius in some infinite regular graphs
cites work: New bounds for codes identifying vertices in graphs
cites work: Bounds for codes identifying vertices in the hexagonal grid
cites work: On identifying codes
cites work: On codes identifying vertices in the two-dimensional square lattice with diagonals
cites work: Q4510800
cites work: On the density of identifying codes in the square lattice
cites work: On a new class of codes for identifying vertices in graphs
full work available at URL: s0012-365x(03)00306-6
OpenAlex ID: W2056540960
description: scientific article; zbMATH DE number 2041898