## 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 ^{Γ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 a problem in graph theory, Math. Gaz. 47 (1963) 220222], 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 G, we show that α≤^{Γd}(G) ≤α(1+2ln(nα)).

Original language | English |
---|---|

Pages (from-to) | 452-458 |

Number of pages | 7 |

Journal | Discrete Optimization |

Volume | 8 |

Issue number | 3 |

DOIs | |

Publication status | Published - Aug 2011 |

## Keywords

- Directed domination
- Independence number
- Oriented graph

## ASJC Scopus subject areas

- Theoretical Computer Science
- Computational Theory and Mathematics
- Applied Mathematics