An optimal strongly identifying code in the infinite triangular grid



: Honkala Iiro

Publisher: ELECTRONIC JOURNAL OF COMBINATORICS

: 2010

: The Electronic Journal of Combinatorics

: ELECTRONIC JOURNAL OF COMBINATORICS

: ELECTRON J COMB

: R91

: 1

: 17

: 1

: 10

: 1077-8926

: http://www.combinatorics.org/ojs/index.php/eljc/article/view/v17i1r91

: https://research.utu.fi/converis/portal/Publication/1873118


Assume that G = (V, E) is an undirected graph, and C subset of V. For every v is an element of V, we denote by I(v) the set of all elements of C that are within distance one from v. If the sets I(v){v} for v is an element of V are all nonempty, and, moreover, the sets {I(v), I(v){v}} for v is an element of 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.

Last updated on 2024-26-11 at 21:53