OLD trees with maximum degree three - Seo, Suk J.; Slater, Peter J. (Utilitas Mathematica, 2014)
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 Tn of order n we have [n/2] + 1 < OLD(T n)< n- 1. Here it is shown that OLD{Tn) < (5/6) n for a tree Tn of order n ≥ 8 with Δ( Tn)=3, and the bound is sharp.