Gimbel, John; Van Gordon, Brian D.; Nicolescu, Mihaela; Umstead, Cherie; Vaiana, Nicole Location with dominating sets. (English) Zbl 0996.05095 Congr. Numerantium 151, 129-144 (2001). Let \(G=(V,E)\) be a graph. The neighborhood \(N(v)\) is defined as a set containing vertex \(v\) itself and all adjacent vertices to \(v\). A dominating vertex set \(S\) is said to be differentiating when for any two distinct verices \(u\) and \(v\) the inequality \(S\cap N(v)\neq S\cap N(u)\) holds. The minimal cardinality of a set \(S\) with the above properties is called differentiating number and denoted as \(\gamma _{D}(G)\). In the paper are given some estimations of \(\gamma _{D}(G)\) for general graphs. Theoretical upper and lower bounds for \(\gamma _{D}(G)\) are given. In the second part exact values of \(\gamma _{D}(G)\) for special classes of graphs as cycles and paths are presented. Some estimations of \(\gamma _{D}(T) \) depending on the order and the number of leaves of a tree \(T\) are presented. Reviewer: Ludovit Niepel (Bratislava) Cited in 14 Documents MSC: 05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) Keywords:dominating set; differentiating set; differentiating number PDFBibTeX XMLCite \textit{J. Gimbel} et al., Congr. Numerantium 151, 129--144 (2001; Zbl 0996.05095)