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
    0 references

    Identifiers