Open neighborhood locatingdominating in trees
For a graph G G that models a facility or a multiprocessor network, detection devices can be placed at the vertices so as to identify the location of an intruder such as a thief or saboteur or a faulty processor. Open neighborhood locatingdominating sets are of interest when the intruder/fault at a vertex precludes its detection at that location. The parameter OLD ( G ) denotes the minimum cardinality of a vertex set S?V(G) S ? V ( G ) such that for each vertex v v in V(G) V ( G ) its open neighborhood N(v) N ( v ) has a unique non-empty intersection with S S . For a tree Tn T n of order n n we have ? n / 2 ? + 1 ? OLD ( T n ) ? n ? 1 . We characterize the trees that achieve these extremal values.
open neighborhood locatingdominating set domination