Codes for identification in the king lattice (Q1423495): Difference between revisions
From MaRDI portal
Set OpenAlex properties. |
Normalize DOI. |
||
Property / DOI | |||
Property / DOI: 10.1007/s00373-003-0531-2 / rank | |||
Property / DOI | |||
Property / DOI: 10.1007/S00373-003-0531-2 / rank | |||
Normal rank |
Latest revision as of 20:05, 10 December 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Codes for identification in the king lattice |
scientific article |
Statements
Codes for identification in the king lattice (English)
0 references
4 March 2004
0 references
Let \(G=(V,E)\) be an undirected graph and \(C\subseteq V\). Let \(B_{r}(F)\) denote the set of all vertices that are within distance \(r\) from at least one vertex in \(F\). If the sets \(B_{r}(F)\cap C\) are distinct for all subsets \(F\) of \(V\) with at most \(k\) elements, then \(C\) is called an \((r,\leq k)\)-identifying code in \(G\). In this paper the graph \(G\) is the two-dimensional square lattice with diagonals. Its vertex set is \(V=\mathbb{Z}^{2}\), and two vertices are connected by an edge if their Euclidean distance is at most \(\sqrt{2}\). The density of \(C\) is defined as \(D(C)=\limsup _{n\rightarrow \infty}| C\cap Q_{n}| /| Q_{n}| \), where \(Q_{n}\) denotes the set of vertices \((x,y)\in V\) with \(| x| \leq n\) and \(| y| \leq n\). It is shown that the optimal density of an \((r,\leq 2)\)-identifying code is \(1/4\) for all \(r\geq 3\). For \(r=1,2\), constructions with densities \(3/7\) and \(3/10\) are given, and the corresponding lower bounds \(9/22\) and \(31/120\) are proved. Notice that the problem of determining the optimal density of an \((r,\leq k)\)-identifying code has been settled for all values of \(r\geq 1\) when \(k=1\).
0 references
optimal density
0 references
identifying code
0 references
graph distance
0 references
square lattice
0 references