Directed Domination in Oriented Graphs

Original · EN

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), which 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 Erdös [Math. Gaz. 47 (1963), 220--222], albeit in disguised form. We extend this notion to directed domination of all graphs. If α denotes the independence number of a graph G, we show that if G is a bipartite graph, we show that Γd(G) = α. We present several lower and upper bounds on the directed domination number.