## 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