| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 421216 | Discrete Applied Mathematics | 2012 | 11 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 by Γ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 Schütte problem, Math. Gaz. 47 (1963) 220–222], albeit in disguised form. The authors [Y. Caro, M.A. Henning, A Greedy partition lemma for directed domination, Discrete Optim. 8 (2011) 452–458] recently extended this notion to directed domination of all graphs. In this paper we continue this study of directed domination in graphs. We show that the directed domination number of a bipartite graph is precisely its independence number. Several lower and upper bounds on the directed domination number are presented.
