Opuscula Math. 29, no. 1 (), 5-14
http://dx.doi.org/10.7494/OpMath.2009.29.1.5
Opuscula Mathematica

# Vertices belonging to all or to no minimum locating dominating sets of trees

Abstract. A set $$D$$ of vertices in a graph $$G$$ is a locating-dominating set if for every two vertices $$u$$, $$v$$ of $$G \setminus D$$ the sets $$N(u) \cap D$$ and $$N(v) \cap D$$ are non-empty and different. In this paper, we characterize vertices that are in all or in no minimum locating dominating sets in trees. The characterization guarantees that the $$\gamma_L$$-excellent tree can be recognized in a polynomial time.
Keywords: domination, locating domination.
Mathematics Subject Classification: 05C69.