Article ID Journal Published Year Pages File Type
420202 Discrete Applied Mathematics 2011 6 Pages PDF
Abstract

For a graph GG 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 locating–dominating 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 vv in V(G)V(G) its open neighborhood N(v)N(v) has a unique non-empty intersection with SS. For a tree TnTn of order nn we have ⌈n/2⌉+1≤OLD(Tn)≤n−1. We characterize the trees that achieve these extremal values.

Keywords
Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics
Authors
, ,