Author/Authors :
Jean E. Dunbar، نويسنده , , Jerrold W. Grossman، نويسنده , , Johannes H. Hattingh، نويسنده , , Stephen T. Hedetniemi، نويسنده , , Alice A. McRae، نويسنده ,
Abstract :
A 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.
