OLD trees with maximum degree three (Q2878227)

Let \(G\) be a graph, and let \(\mathcal{S}=\{S_1, \dots, S_p\}\) (where, for all \(i \in [1, p],\) \(S_i \subset V(G)\)) be such that \(\bigcup_{i=1}^p S_i=V(G),\) then \(\mathcal{S}\) is a distinguishing set of \(G\) if, for every pair of vertices in \(V(G),\) some \(S_i\) contains exactly one of them. Several related notions have been defined. In particular, let \(S =\{w_1, \dots, w_q\}\) (where, for all \(i \in [1, q]\), \(w_i \in V(G)\)), \(S\) is an open-locating-dominating set of \(G\) if \(\{N(w_1), \dots, N(w_q)\}\) is a distinguishing set of \(G.\) Here, for a vertex \(v \in V(G)\), \(N(v)\) refers to its open neighbors, i.e., all the vertices adjacent to \(v\), excluding \(v\) itself.NEWLINENEWLINENEWLINELet \(\mathrm{OLD}(G)\) further denote the cardinality of a minimum open-locating-dominating set of a graph \(G\). It was previously shown that, for \(T_n\) (a tree of order \(n\)), \(\lceil n/2 \rceil+1 \leq \mathrm{OLD}(T_n) \leq n-1\).NEWLINENEWLINENEWLINEIn this paper, the authors show that, in the tree \(T_{2k}\) for which \(\mathrm{OLD}(T_{2k})=2k-1\), there exists only one vertex whose degree is 4. They further show, with a detailed case analysis, that \(\mathrm{OLD}(T_n) \leq (5/6)n\) for \(n \geq 8,\) with \(\Delta(T_n)=3.\) The above bound is actually sharp.