On weakly connected domination in graphs

AbstractA weakly connected dominating set for a connected graph is a dominating set D of vertices of the graph such that the edges not incident to any vertex in D do not separate the graph. This paper considers the weakly connected domination number, γw, and related domination parameters. It is shown that the problem of computing γw is NP-hard in general but linear for trees. In addition, several sharp upper and lower bounds for γw are obtained