OLD trees with maximum degree three

Abstract

For a graph G that models a facility or a multi-processor 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) such that for each vertex V in V(G) its open neighborhood N(V) has a unique non-empty intersection with S. For a tree T_n of order n we have [n/2] + 1 < OLD(T _n)< n- 1. Here it is shown that OLD{T_n) < (5/6) n for a tree T_n of order n ≥ 8 with Δ( T_n)=3, and the bound is sharp.