2010/10/12 by Yair Caro, Caro, Yair, Michael A. Henning +1
Computer Science · Mathematics · #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #math.CO #msc:05C69
paper · pdf · doi:10.48550/arxiv.1010.2467
12 pages
arxiv created 2010/10/12 · openalex publication_date 2010/10/12 · arxiv updated 2010/10/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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. 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/α)).