论文标题
直接产品图的配对和上部支配不平等的紧密度
Tightness of Paired and Upper Domination Inequalities for Direct Product Graphs
论文作者
论文摘要
如果每个顶点$ g $在$ d $中或与$ d $的顶点相邻，则图$ g $中的$ d $ $ d $。成对的支配数字$γ_ {\ mathrm {pr}}（g）$ g $的$是一个统治集的最小尺寸，其诱导子图的最小匹配能够完美匹配，并且上部支配数字$γ（g）$是最小统治集的最大尺寸。在本文中，我们研究了这些统治参数的两个乘法不平等的清晰度，其中图产品是直接乘积$ \ times $。 我们表明，对于每个正常数$ c $，存在图$ g $和任意大直径的$ h $，以至于$γ_ {\ mathrm {pr}}}（g \ times h）\ leqcγ_{\ mathrm {pr}}（pr}}（pr}}}（g） Paulraja和Sampath Kumar的作品。然后，我们研究这种不平等的何时以$ c = \ frac {1} {2} $，特别是证明它在$ g $和$ h $是树时都能保留。最后，我们证明了由于Brešar，Klavžar和Rall引起的不平等$γ（G \ times h）\ geqγ（g）γ（h）$很紧。
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.
