Domination in digraphs and their products

Boštjan Brešar, Kirsti Kuenzel, Douglas F. Rall

Published 2020-07-30Version 1

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^{\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), $\gamma_t(T)=\rho^{\rm 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\mathbin{\Box} T)\ge\gamma(G)\gamma(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 $\gamma(G)\ge\gamma(H)$, we have $\gamma(G \mathbin{\Box} 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\mathbin{\Box} H)=\gamma(T)\gamma(H)$ are also investigated.