An optimal strongly identifying code in the infinite triangular grid (Q986692)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An optimal strongly identifying code in the infinite triangular grid |
scientific article |
Statements
An optimal strongly identifying code in the infinite triangular grid (English)
0 references
12 August 2010
0 references
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.
0 references
graph
0 references
identifying code
0 references
triangular grid
0 references
density
0 references