A Greedy Partition Lemma for Directed Domination

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. 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 $\alpha$ denotes the independence number of a graph $G$, we show that $\alpha \le {\Gamma }_d(G)\le \alpha (1+2\ln (n/\alpha ))$.

12 pages