On Weak Domination in Graphs

Abstract

Sampathkumar and Pushpa Latha (see $[3]$) conjectured that the independent domination number, $i(T)$, of a tree $T$ is less than or equal to its weak domination number, ${\gamma }_w(T)$. We show that this conjecture is true, prove that ${\gamma }_w(T)\le \beta (T)$ for a tree $T$, exhibit an infinite class of trees in which the differences ${\gamma }_w-i$ and $\beta –{\gamma }_w$ can be made arbitrarily large, and show that the decision problem corresponding to the computation of $\gamma (G)$ is $NP$-complete, even for bipartite graphs. Lastly, we provide a linear algorithm to compute ${\gamma }_w(T)$ for a tree $T$.