An optimal strongly identifying code in the infinite triangular grid
type: Item
instance of: scholarly article
title: An optimal strongly identifying code in the infinite triangular grid
zbMATH Open document ID: 1193.05125
published in: The Electronic Journal of Combinatorics
publication date: 2010-08-12T00:00:00Z
full work available at URL: https://eudml.org/doc/231681
full work available at URL: v17i1r91.html
review text: Summary: Assume that \(G=(V,E)\) is an undirected graph, and \(C\subseteq V\). For every \({\mathbf v}\in V\), we denote by \(I({\mathbf v})\) the set of all elements of \(C\) that are within distance one from \({\mathbf v}\). If the sets \(I({\mathbf v})\setminus\{{\mathbf v}\}\) for \({\mathbf v}\in V\) are all nonempty, and, moreover, the sets \(\{I({\mathbf v}), I({\mathbf v})\setminus \{{\mathbf v}\}\}\) for \({\mathbf v}\in V\) are disjoint, then \(C\) is called a strongly identifying code. The smallest possible density of a strongly identifying code in the infinite triangular grid is shown to be 6/19.
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 5769506
zbMATH Keywords: graph
zbMATH Keywords: identifying code
zbMATH Keywords: triangular grid
zbMATH Keywords: density
author: Iiro Honkala
MaRDI profile type: Publication
Recommended article: Optimal identifying codes in the infinite 3-dimensional king grid
Recommended article: Identifying codes for infinite triangular grids with a finite number of rows
Recommended article: An optimal edge-robust identifying code in the triangular lattice
Recommended article: The number of completely different optimal identifying codes in the infinite square grid
Recommended article: Lower bounds for identifying codes in some infinite grids
Recommended article: New bounds on the minimum density of an identifying code for the infinite hexagonal grid
Recommended article: Optimal lower bound for 2-identifying codes in the hexagonal grid
Recommended article: On Identifying Codes in the Triangular and Square Grids
Recommended article: A new lower bound on the density of vertex identifying codes for the infinite hexagonal grid
Recommended article: Minimum-Density Identifying Codes in Square Grids
description: scientific article; zbMATH DE number 5769506