The minimum density of an identifying code in the king lattice.

DOI10.1016/S0012-365X(03)00306-6MaRDI QIDQ1422415zbMATH OpenOpenAlexFDO

Authors Irène Charon, Olivier Hudry, Iiro Honkala, Antoine Lobstein

Publication date 14 February 2004

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(03)00306-6

zbMATH Keywords

distance square lattice

Mathematics Subject Classification ID

Distance in graphs (05C12) Applications of graph theory (05C90) Combinatorial codes (94B25) Bounds on codes (94B65)

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\).

Recommendations

Cites work

Cited in

(31)

This page was built for publication: The minimum density of an identifying code in the king lattice.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1422415)