Mathematics – Combinatorics
Scientific paper
2010-10-12
Mathematics
Combinatorics
18 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. We extend this notion to directed domination of all graphs. If $\alpha$ denotes the independence number of a graph $G$, we show that if $G$ is a bipartite graph, we show that $\Gamma_d(G) = \alpha$. We present several lower and upper bounds on the directed domination number.
Caro Yair
Henning Michael A.
No associations
LandOfFree
Directed Domination in Oriented Graphs 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 Directed Domination in Oriented Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Directed Domination in Oriented Graphs will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-608913