Periodicity of identifying codes in strips

DOI10.1016/J.IPL.2018.03.007MaRDI QIDQ1708274zbMATH OpenOpenAlexFDO

Authors Minghui Jiang

Publication date 5 April 2018

Published in Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

graph algorithmsidentifying codeminimum cycle mean

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial codes (94B25) Applications of graph theory to circuits and networks (94C15)

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_4$ with the minimum density $11/28$, and a periodic identifying code in $S_5$ with the minimum density $19/50$.

Recommendations

• Identifying codes in some subgraphs of the square lattice
• Minimum-Density Identifying Codes in Square Grids
• Lower bounds for identifying codes in some infinite grids
• Minimum density of identifying codes of king grids
• Minimum density of identifying codes of king grids

Cites work

• scientific article; zbMATH DE number 1017008 (Why is no real title available?)
• A characterization of the minimum cycle mean in a digraph
• Exact Minimum Density of Codes Identifying Vertices in the Square Grid
• Identifying codes in some subgraphs of the square lattice
• Introduction to algorithms.
• Minimum-Density Identifying Codes in Square Grids
• New bounds for codes identifying vertices in graphs
• On a new class of codes for identifying vertices in graphs

Cited in

(6)

• Identifying codes in some subgraphs of the square lattice
• Locating-domination and identification
• Minimum density of identifying codes of king grids
• Minimum density of identifying codes of king grids
• Optimal identifying codes of two families of Cayley graphs
• Density of identifying codes of hexagonal grids with finite number of rows

This page was built for publication: Periodicity of identifying codes in strips

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1708274)