Domination in digraphs and their products

Abstract

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 $\gamma (D)$ (respectively,${\gamma }_t(D)$). The maximum number of pairwise disjoint closed (respectively,open) in-neighborhoods of $D$ is denoted by $\rho (D)$ (respectively,${\rho }^{\mathrm{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), ${\gamma }_t(T)={\rho }^{\mathrm{o}}(T)$ and $\gamma (T)=\rho (T)$. By using the former equality we then prove that ${\gamma }_t(G\times T)={\gamma }_t(G){\gamma }_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 $\gamma (T)=\rho (T)$ we derive the bound $\gamma (G\square T)\ge \gamma (G)\gamma (T)$, where $G$ is an arbitrary digraph, $T$ an arbitrary ditree and $G\square T$ is their Cartesian product. In general digraphs this Vizing-type bound fails, yet we prove that for any digraphs $G$ and $H$, where $\gamma (G)\ge \gamma (H)$, we have $\gamma (G\square H)\ge \frac{1}{2}\gamma (G)(\gamma (H)+1)$. This inequality is sharp as demonstrated by an infinite family of examples. Ditrees $T$ and digraphs $H$ enjoying $\gamma (T\square H)=\gamma (T)\gamma (H)$ are also investigated.

22 pages and 5 figures