Open-locating-dominating sets in the infinite king grid

摘要

For a graph G that models a facility, detection devices can be placed at the vertices in order to identify the location of an intruder such as a thief or saboteur. We consider the open-locating-dominating set problem, which deals with the situation in which the intruder at a vertex can interfere with the detection device located there. A set S of vertices in a graph G = (V(G),E(G)) is an open-locating-dominating set (OLD-set) for G if for every two vertices u, v of V(C) the sets N(u) n D and N(v) D D are non-empty and different. The open-locating-dominating number OLD(G) is the minimum cardinality of an OLD-set for G. We continue the study of the OLD-set problem and describe minimum density OLD-sets for the infinite king grid.