Codes for identification in the king lattice (Q1423495)

From MaRDI portal
Revision as of 11:05, 10 February 2024 by RedirectionBot (talk | contribs) (‎Removed claims)
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
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references