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.
Reviewer: B.Zelinka

05C35 Extremal problems in graph theory
05C05 Trees
05C99 Graph theory