zbMATH — the first resource for mathematics

Efficient dominating sets in graphs. (English) Zbl 0664.05027
Applications of discrete mathematics, Proc. 3rd SIAM Conf., Clemson/South Carolina 1986, 189-199 (1988).
[For the entire collection see Zbl 0655.00007.]
A subset D of the vertex set V(G) of a graph G is called dominating, if for each vertex $$x\in V(G)-D$$ there exists a vertex $$y\in D$$ adjacent to x. If any two vertices of a dominating set D in a graph G have the distance at least 3, the set D is called an efficient dominating set in G. It is proved that the problem to determine whether a given graph has an efficient dominating set is NP-complete. A constructive characterization of trees having an efficient dominating set and of trees having two disjoint efficient dominating sets is presented.