论文标题
Digraphs及其产品的统治
Domination in digraphs and their products
论文作者
论文摘要
$ d $中的一组digraph $ d $的主导（分别为总体统治）集合的$ s $是$ d $的一组顶点，以使$ s $的封闭（分别是，开放）的邻近（分别为开放）的顶点等于$ d $的顶点。 $ d $的支配（分别为总支配）集的最小大小是$ d $的统治（分别为总统治），分别表示$γ（d）$（分别为$γ_t（d）$）。 $ρ（d）$（分别为$ρ^{\ rm o}（d）$）表示最大的成对脱节数量（分别为$ d $）$ d $ $ d $。我们证明，在Digraphs中，其基础图至少$ 7 $，封闭式（分别，开放）内孔室享有Helly的属性，并使用这两个结果证明，在任何有点$ t $中（即，基础图形是一棵树），$γ_t（t），$γ_t（t）= p（t） $γ（t）=ρ（t）$。然后，我们使用以前的平等性证明$γ_T（g \ times t）=γ_t（g）γ_T（t）$，其中$ g $是任何digraph，$ t $都是任何ditree，每个都没有源顶点，而$ g \ times t $ t $ t $是他们的直接产品。从平等$γ（t）=ρ（t）$中，我们得出了绑定的$γ（g \ m arthbin {\ box} t）\geγ（g）γ（t）$，其中$ g $是任意的挖掘，$ t $ $ t $是任意的ditree，$ g \ g \ g \ g \ m \ \ box {\ box {\ box} t $是他们的Cartesian产品。总的来说，这种较为型的型限制失败了，但是我们证明，对于任何digraphs $ g $和$ h $这种不平等是无限的示例家族所证明的。还研究了ditrees $ t $ and digraphs $ h $享受$γ（t \ mathbin {\ box} h）=γ（t）γ（h）$。
A dominating (respectively, total dominating) set $S$ of a digraph $D$ is a set of vertices in $D$ such that the union of the closed (respectively, open) out-neighborhoods of vertices in $S$ equals the vertex set of $D$. The minimum size of a dominating (respectively, total dominating) set of $D$ is the domination (respectively, total domination) number of $D$, denoted $γ(D)$ (respectively,$γ_t(D)$). The maximum number of pairwise disjoint closed (respectively,open) in-neighborhoods of $D$ is denoted by $ρ(D)$ (respectively,$ρ^{\rm o}(D)$). We prove that in digraphs whose underlying graphs have girth at least $7$, the closed (respectively,open) in-neighborhoods enjoy the Helly property, and use these two results to prove that in any ditree $T$ (that is, a digraph whose underlying graph is a tree), $γ_t(T)=ρ^{\rm o}(T)$ and $γ(T)=ρ(T)$. By using the former equality we then prove that $γ_t(G\times T)=γ_t(G)γ_t(T)$, where $G$ is any digraph and $T$ is any ditree, each without a source vertex, and $G\times T$ is their direct product. From the equality $γ(T)=ρ(T)$ we derive the bound $γ(G\mathbin{\Box} T)\geγ(G)γ(T)$, where $G$ is an arbitrary digraph, $T$ an arbitrary ditree and $G\mathbin{\Box} T$ is their Cartesian product. In general digraphs this Vizing-type bound fails, yet we prove that for any digraphs $G$ and $H$, where $γ(G)\geγ(H)$, we have $γ(G \mathbin{\Box} H) \ge \frac{1}{2}γ(G)(γ(H) + 1)$. This inequality is sharp as demonstrated by an infinite family of examples. Ditrees $T$ and digraphs $H$ enjoying $γ(T\mathbin{\Box} H)=γ(T)γ(H)$ are also investigated.
