Mathematics – Combinatorics
Scientific paper
2010-10-12
Mathematics
Combinatorics
12 pages
Scientific paper
A directed dominating set in a directed graph $D$ is a set $S$ of vertices of $V$ such that every vertex $u \in V(D) \setminus S$ has an adjacent vertex $v$ in $S$ with $v$ directed to $u$. The directed domination number of $D$, denoted by $\gamma(D)$, is the minimum cardinality of a directed dominating set in $D$. The directed domination number of a graph $G$, denoted $\Gamma_d(G)$, which is the maximum directed domination number $\gamma(D)$ over all orientations $D$ of $G$. The directed domination number of a complete graph was first studied by Erd\"{o}s [Math. Gaz. 47 (1963), 220--222], albeit in 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 $\alpha$ denotes the independence number of a graph $G$, we show that $\alpha \le \Gamma_d(G) \le \alpha(1+2\ln(n/\alpha))$.
Caro Yair
Henning Michael A.
No associations
LandOfFree
A Greedy Partition Lemma for Directed Domination does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A Greedy Partition Lemma for Directed Domination, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Greedy Partition Lemma for Directed Domination will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-608922