On weak domination in graphs (Q2713615)

A subset \(S\) of the vertex set \(V(G)\) of a graph \(G\) is called dominating in \(G\), if for each \(u\in V(G)-S\) there exists \(v\in S\) adjacent to \(u\). If for each \(u\in V(G) - S\) there exists \(v\in S\) adjacent to \(u\) and having degree less than or equal to that of \(u\), then \(S\) is called weakly dominating in \(G\). A subset of \(V(G)\) is independent, if it consists of pairwise non-adjacent vertices. The minimum number of vertices of a set which is simultaneously dominating and independent is the independent domination number \(i(G)\) of \(G\), the minimum number of vertices of a weakly dominating set is the weak domination number \(\gamma _w(G)\) of \(G\) and the maximum number of vertices of an independent set in \(G\) is the independence number \(\beta (G)\) of \(G\). For a tree \(T\) the inequalities \(i(T) \leq \gamma _w (T)\) and \(\gamma _w(T) \leq \beta (T)\) are proved. It is also proved that the differences \(\gamma _w (T) - i(T)\) and \(\beta (T) - \gamma _w(T)\) may be arbitrarily large. The NP-completeness of finding \(\gamma _w(G)\) is shown for graphs \(G\) in general and a linear algorithm for computing \(\gamma _w(T)\) for a tree \(T\) is presented.