A Greedy Partition Lemma for directed domination

A directed dominating set in a directed graph $D$ is a set $S$ of vertices of $V$ such that every vertex $u\in V\left(D\right)\backslash S$ has an adjacent vertex $v$ in $S$ with $v$ directed to $u$ . The directed domination number of $D$ , denoted by $\gamma \left(D\right)$ , is the minimum cardinality of a directed dominating set in $D$ . The directed domination number of a graph $G$ , denoted $G_d\left(G\right)$ , is the maximum directed domination number $\gamma \left(D\right)$ over all orientations $D$ of $G$ . The directed domination number of a complete graph was first studied by Erdos (1963), albeit in a disguised form. In this paper we prove a Greedy Partition Lemma for directed domination in oriented graphs. Applying this lemma, we obtain bounds on the directed domination number. In particular, if $a$ denotes the independence number of a graph $G$ , we show that $a=G_d\left(G\right)=a(1+2ln(n/a))$ .