Twin Domination in Digraphs

Abstract

A vertex $v$ in a digraph $D$ out-dominates itself as well as all vertices $u$ such that $(v,u)$ is an arc of $D$; while $v$ in-dominates both itself and all vertices $w$ such that $(w,v)$ is an arc of $D$. A set $S$ of vertices of $D$ is a twin dominating set of $D$ if every vertex of $D$ is out-dominated by some vertex of $S$ and in-dominated by some vertex of $S$. The minimum cardinality of a twin dominating set is the twin domination number ${\gamma }^{\ast }(D)$ of $D$. It is shown that ${\gamma }^{\ast }(D)\le \frac{2p}{3}$ for every digraph $D$ of order $p$ having no vertex of in-degree $0$ or out-degree $0$. Moreover, we give a Nordhaus-Gaddum type bound for ${\gamma }^{\ast }$, and for transitive digraphs we give a sharp upper bound for the twin domination number in terms of order and minimum degree.

For a graph $G$, the upper orientable twin domination number $DO{M}^{\ast }(G)$ is the maximum twin domination number ${\gamma }^{\ast }(D)$ over all orientations $D$ of $G$; while the lower orientable twin domination number $do{m}^{\ast }(G)$ of $G$ is the minimum such twin domination number. It is shown that for each graph $G$ and integer $c$ with $do{m}^{\ast }(G)\le c\le DO{M}^{\ast }(G)$, there exists an orientation $D$ of $G$ such that ${\gamma }^{\ast }(D)=c$.