Directed Domination in Oriented Graphs

Abstract

A directed dominating set in a directed graph $D$ is a set $S$ of vertices of $V$ such that every vertex $u\in V(D)\setminus S$ has an adjacent vertex $v$ in $S$ with $v$ directed to $u$. The directed domination number of $D$, denoted by $\gamma (D)$, is the minimum cardinality of a directed dominating set in $D$. The directed domination number of a graph $G$, denoted ${\Gamma }_d(G)$, which is the maximum directed domination number $\gamma (D)$ over all orientations $D$ of $G$. The directed domination number of a complete graph was first studied by Erdös [Math. Gaz. 47 (1963), 220--222], albeit in disguised form. We extend this notion to directed domination of all graphs. If $\alpha$ denotes the independence number of a graph $G$, we show that if $G$ is a bipartite graph, we show that ${\Gamma }_d(G)=\alpha$. We present several lower and upper bounds on the directed domination number.

18 pages