2010/04/19 by Ryan R. Martin, Martin, Ryan, Brendon Stanton +1
Computer Science · Engineering · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Interconnection Networks and Systems #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1004.3281
openalex publication_date 2010/04/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An r-identifying code on a graph G is a set C⊂ 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.