Total domination and least domination in a tree (Q1874378): Difference between revisions

A subset \(X\) of the vertex set \(V(G)\) of a graph \(G\) is called dominating (or total dominating) in \(G\), if for each \(x\in V(G)- X\) (or for each \(x\in V(G)\), respectively) there exists \(y\in X\) adjacent to \(x\). The least number of vertices of a dominating (or total dominating) set in \(G\) is the domination number \(\gamma(G)\) (or the total domination number \(\gamma_t(G)\), respectively) of \(G\). Let \([X]\) denote the subgraph of \(G\) induced by a set \(X\subseteq V(G)\). A dominating set \(X\) of \(G\) is a least dominating set in \(G\), if \(\gamma([X])\leq \gamma([X_1])\) for each dominating set \(X_1\) of \(G\). The minimum number of vertices of such a set is the least domination number \(\gamma_\ell(G)\) of \(G\). The authors prove the following conjecture by O. Favaron: For every tree \(T\) the inequality \(\gamma_t(T)\gamma_\ell(T)\leq 3/2\) holds.