Vertex identifying codes for the n-dimensional lattice

zbMATH Open1261.94040arXiv1008.4892MaRDI QIDQ2906869FDOQ2906869

Authors: Brendon Stanton 

Publication date: 5 September 2012

Published in: The Australasian Journal of Combinatorics (Search for Journal in Brave)

Abstract: An $r$-identifying code on a graph $G$ is a set $CsubsetV(G)$ such that for every vertex in $V(G)$, the intersection of the radius-$r$ closed neighborhood with $C$ is nonempty and different. Here, we provide an overview on codes for the $n$-dimensional lattice, discussing the case of 1-identifying codes, constructing a sparse code for the 4-dimensional lattice as well as showing that for fixed $n$, the minimum density of an $r$-identifying code is $Theta(1/r^{n-1})$.

Full work available at URL: https://arxiv.org/abs/1008.4892

Recommendations

• On codes identifying vertices in the two-dimensional square lattice with diagonals
• Construction of codes identifying sets of vertices
• On a new class of codes for identifying vertices in graphs
• Identifying codes in some subgraphs of the square lattice
• Constructing codes identifying sets of vertices
• Vertex codes of graphs
• On codes identifying sets of vertices in Hamming spaces
• scientific article; zbMATH DE number 2081125
• On the density of identifying codes in the square lattice
• New bounds for codes identifying vertices in graphs

Mathematics Subject Classification ID

Applications of graph theory (05C90) Geometric methods (including applications of algebraic geometry) applied to coding theory (94B27)

Cited In (5)

• Optimal identifying codes in the infinite 3-dimensional king grid
• On identifying codes
• Identifying codes of corona product graphs
• Optimal identifying codes of two families of Cayley graphs
• Improved upper bounds for identifying codes in \(n\)-dimensional \(q\)-ary cubes

This page was built for publication: Vertex identifying codes for the \(n\)-dimensional lattice

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