On the domination of the products of graphs II: Trees

For a graph G , a subset of vertices D is a dominating set if for each vertex X not in D , X is adjacent to at least one vertex of D. The domination number, γ( G ), is the order of the smallest such set. An outstanding conjecture in the theory of domination is for any two graph G and H ,\documentclass{article}\pagestyle{empty}\begin{document}$$ \gamma \left({{\rm G} \times {\rm H}} \right) \ge \gamma \left(G \right)\gamma \left(H \right) $$\end{document}One result presented in this paper settles this question in the case when at least one of G or H is a tree. We show that\documentclass{article}\pagestyle{empty}\begin{document}$$ \gamma \left({G \times T} \right) \ge \gamma \left(G \right)\gamma \left(T \right) $$\end{document}for all graphs G and any tree T. Furthermore, we supply a partial characterization for which pairs of trees, T 1 and T 2 , strict inequality occurs. We show\documentclass{article}\pagestyle{empty}\begin{document}$$ \gamma \left({T_1 \times T_1 } \right)\gamma \left({T_1 } \right)\gamma \left({T_2 } \right) $$\end{document}for almost all pairs of trees.