| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 1141649 | Discrete Optimization | 2011 | 7 Pages |
A directed dominating set in a directed graph DD is a set SS of vertices of VV such that every vertex u∈V(D)∖Su∈V(D)∖S has an adjacent vertex vv in SS with vv directed to uu. The directed domination number of DD, denoted by γ(D)γ(D), is the minimum cardinality of a directed dominating set in DD. The directed domination number of a graph GG, denoted Γd(G)Γd(G), is the maximum directed domination number γ(D)γ(D) over all orientations DD of GG. The directed domination number of a complete graph was first studied by Erdős [P. Erdős On a problem in graph theory, Math. Gaz. 47 (1963) 220–222], 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 αα denotes the independence number of a graph GG, we show that α≤Γd(G)≤α(1+2ln(n/α))α≤Γd(G)≤α(1+2ln(n/α)).
