Vertex identifying codes for the n-dimensional lattice

MaRDI QIDQ2906869zbMATHFDO

Authors Brendon Stanton

Publication date 5 September 2012

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

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

Mathematics Subject Classification ID

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

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})$.

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

Cited in

(5)

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

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)