Vertex identifying codes for the n-dimensional lattice

zbMATH Open1261.94040arXiv1008.4892MaRDI QIDQ2906869FDOQ2906869

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

Mathematics Subject Classification ID

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

Cited In (4)

• 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

   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 👍 👎
• Title not available (Why is that?) 👍 👎
• On the density of identifying codes in the square lattice 👍 👎
• New bounds for codes identifying vertices in 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)