Tightness of Paired and Upper Domination Inequalities for Direct Product Graphs

Abstract

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 ${\gamma }_{\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 $\Gamma (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 ${\gamma }_{\mathrm{pr}}(G\times H)\le c{\gamma }_{\mathrm{pr}}(G){\gamma }_{\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 $\Gamma (G\times H)\ge \Gamma (G)\Gamma (H)$, due to Brešar, Klavžar, and Rall, is tight.

15 pages, 3 figures

References in corpus (1)

• An Improved Bound for Upper Domination of Cartesian Products of Graphs