Paper detail

Tightness of Paired and Upper Domination Inequalities for Direct Product Graphs

A set $D$ of vertices in a graph $G$ is called dominating if every vertex of $G$ is either in $D$ or adjacent to a vertex of $D$. The paired domination number $γ_{\mathrm{pr}}(G)$ of $G$ is the minimum size of a dominating set whose induced subgraph admits a perfect matching, and the upper domination number $Γ(G)$ is the maximum size of a minimal dominating set. In this paper, we investigate the sharpness of two multiplicative inequalities for these domination parameters, where the graph product is the direct product $\times$. We show that for every positive constant $c$, there exist graphs $G$ and $H$ of arbitrarily large diameter such that $γ_{\mathrm{pr}}(G \times H) \leq cγ_{\mathrm{pr}}(G)γ_{\mathrm{pr}}(H)$, thus answering a question of Rall as well as two questions of Paulraja and Sampath Kumar. We then study when this inequality holds with $c = \frac{1}{2}$, in particular proving that it holds whenever $G$ and $H$ are trees. Finally, we demonstrate that the inequality $Γ(G \times H) \geq Γ(G) Γ(H)$, due to Brešar, Klavžar, and Rall, is tight.