Periodicity of identifying codes in strips

2016/07/13 by Minghui Jiang, Jiang, Minghui · 1 citation
Computer Science · Mathematics · #Algorithms and Data Compression #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Limits and Structures in Graph Theory #Machine Learning and Algorithms

paper · pdf · doi:10.48550/arxiv.1607.03848

openalex publication_date 2016/07/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

An identifying code in a graph is a subset of vertices having a nonempty and distinct intersection with the closed neighborhood of every vertex. We prove that the infimum density of any identifying code in S_k (an infinite strip of k rows in the square grid) can always be achieved by a periodic identifying code with pattern length at most 2^4k. Assisted by a compute program implementing Karp's algorithm for minimum cycle mean, we find a periodic identifying code in S₄ with the minimum density 11/28, and a periodic identifying code in S₅ with the minimum density 19/50.

Cited by

• Optimal and quasi-optimal locating-dominating densities in the infinite hexagonal grid with a finite number of rows

Related

• Lower bounds for identifying codes in some infinite grids
• Optimal lower bound for 2-identifying code in the hexagonal grid
• The Identifying Code problem on P₄-tidy graphs
• New lower bound for 2-identifying code in the square grid
• Vertex identifying codes for the n-dimensional lattice