Open neighborhood locating dominating sets.
Suk J. Seo, Peter J. Slater · 2010
For a graph G that models a facility, various detection devices can be placed at the vertices so as to identify the location of an intruder such as a thief or saboteur. Here we introduce the open neighborhood locating-dominating set problem. This deals with problems in which the intruder at a vertex can interfere with the detection device located there. We seek a minimum cardinality vertex set S with the property that for each vertex v its open neighborhood N(v) has a unique non-empty intersection with S. Such a set is an OLD-set for G. Among other things, we describe minimum density OLD-sets for various infinite grid graphs.