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(D) \setminus S$ has an adjacent vertex $v$ in $S$ with $v$ directed to $u$. The directed domination number of $D$, denoted by $γ(D)$, is the minimum cardinality of a directed dominating set in $D$. The directed domination number of a graph $G$, denoted $Γ_d(G)$, which is the maximum directed domination number $γ(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 $α$ denotes the independence number of a graph $G$, we show that $α\le Γ_d(G) \le α(1+2\ln(n/α))$.

No reviews yet.

No comments yet.