Optimal lower bound for 2-identifying codes in the hexagonal grid

MaRDI QIDQ456287zbMATH OpenFDO

Authors Ville Junnila, Tero Laihonen

Publication date 24 October 2012

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1202.0670, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i2p38

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

hexagonal grididentifying codeoptimal code

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Combinatorics in computer science (68R05) Bounds on codes (94B65) Fault detection; testing in circuits and networks (94C12)

Abstract: An $r$-identifying code in a graph $G=(V,E)$ is a subset $CsubseteqV$ such that for each $uinV$ the intersection of $C$ and the ball of radius $r$ centered at $u$ is non-empty and unique. Previously, $r$-identifying codes have been studied in various grids. In particular, it has been shown that there exists a 2-identifying code in the hexagonal grid with density 4/19 and that there are no 2-identifying codes with density smaller than 2/11. Recently, the lower bound has been improved to 1/5 by Martin and Stanton (2010). In this paper, we prove that the 2-identifying code with density 4/19 is optimal, i.e. that there does not exist a 2-identifying code in the hexagonal grid with smaller density.

Review text

Summary: An \(r\)-identifying code in a graph \(G = (V,E)\) is a subset \(C \subseteq V\) such that for each \(u \in V\) the intersection of \(C\) and the ball of radius \(r\) centered at \(u\) is non-empty and unique. Previously, \(r\)-identifying codes have been studied in various grids. In particular, it has been shown that there exists a 2-identifying code in the hexagonal grid with density 4/19 and that there are no 2-identifying codes with density smaller than 2/11. Recently, the lower bound has been improved to \(1/5\) by \textit{R. Martin} and \textit{B. Stanton} [Electron. J. Comb. 17, No. 1, Research Paper R122, 16 p., electronic only (2010; Zbl 1272.05161)]. In this paper, we prove that the 2-identifying code with density 4/19 is optimal, i.e. that there does not exist a 2-identifying code in the hexagonal grid with smaller density.

Recommendations

• New bounds on the minimum density of an identifying code for the infinite hexagonal grid
• Improved Bounds forr-Identifying Codes of the Hex Grid
• A new lower bound on the density of vertex identifying codes for the infinite hexagonal grid
• Bounds for codes identifying vertices in the hexagonal grid
• New lower bound for 2-identifying code in the square grid
• Lower bounds for identifying codes in some infinite grids
• An improved lower bound for \((1,\leq 2)\)-identifying codes in the king grid
• An optimal strongly identifying code in the infinite triangular grid
• Minimum-Density Identifying Codes in Square Grids
• On identifying codes in the hexagonal mesh

Cited in

(13)

• On identifying codes in the hexagonal mesh
• Lower bounds for identifying codes in some infinite grids
• Identifying codes in the complementary prism of cycles
• A new lower bound on the density of vertex identifying codes for the infinite hexagonal grid
• New lower bound for 2-identifying code in the square grid
• New bounds on the minimum density of an identifying code for the infinite hexagonal grid
• Minimum-Density Identifying Codes in Square Grids
• Improved Bounds forr-Identifying Codes of the Hex Grid
• Locating-domination and identification
• Density of identifying codes of hexagonal grids with finite number of rows
• On Iiro Honkala's contributions to identifying codes
• Optimal local identifying and local locating-dominating codes
• An optimal strongly identifying code in the infinite triangular grid

This page was built for publication: Optimal lower bound for 2-identifying codes in the hexagonal grid

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