Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
420202 | Discrete Applied Mathematics | 2011 | 6 Pages |
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
Suk J. Seo, Peter J. Slater,