×

Location with dominating sets. (English) Zbl 0996.05095

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.

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
PDFBibTeX XMLCite