pith. sign in

arxiv: 1004.3281 · v1 · submitted 2010-04-19 · 🧮 math.CO

Lower bounds for identifying codes in some infinite grids

classification 🧮 math.CO
keywords boundscodecodesdensityfinitegraphgridsidentifying
0
0 comments X
read the original abstract

An $r$-identifying code on a graph $G$ is a set $C\subset V(G)$ such that for every vertex in $V(G)$, the intersection of the radius-$r$ closed neighborhood with $C$ is nonempty and unique. On a finite graph, the density of a code is $|C|/|V(G)|$, which naturally extends to a definition of density in certain infinite graphs which are locally finite. We present new lower bounds for densities of codes for some small values of $r$ in both the square and hexagonal grids.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. On Iiro Honkala's contributions to identifying codes

    cs.DM 2024-02 unverdicted novelty 1.0

    The paper surveys Iiro Honkala's contributions to identifying codes across complexity, combinatorics, grids, graph parameters, structural properties, and optimal code counts.