Opuscula Math. 29, no. 1 (2009), 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.
- Mostafa Blidia
- University of Blida, LAMDA-RO, Department of Mathematics, B.P. 270, Blida, Algeria
- Rahma Lounes
- University of Blida, LAMDA-RO, Department of Mathematics, B.P. 270, Blida, Algeria
- Received: 2007-02-10.
- Revised: 2009-05-02.
- Accepted: 2009-05-11.
