Abstract
A directed dominating set in a directed graph D is a set S of vertices of V such that every vertex u∈V(D)\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 by Γd(G), 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 Erds [P. Erds, On Schtte problem, Math. Gaz. 47 (1963) 220222], albeit in disguised form. The authors [Y. Caro, M.A. Henning, A Greedy partition lemma for directed domination, Discrete Optim. 8 (2011) 452458] 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.
| Original language | English |
|---|---|
| Pages (from-to) | 1053-1063 |
| Number of pages | 11 |
| Journal | Discrete Applied Mathematics |
| Volume | 160 |
| Issue number | 7-8 |
| DOIs | |
| Publication status | Published - May 2012 |
Keywords
- Directed domination
- Independence number
- Oriented graph
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics