Guaranteed existence of a dominating set for special directed graph

Question

Consider an $n$-vertex directed graph $G = (V, E)$ with the property that every vertex has an edge into it. That is, for each $v \in V$, we have that $(u,v)$ is in $E$. I define a dominating set $D \subseteq V$ for $G$ to have the property that for all $v \in V$, either $v \in D$ or $(u,v) \in E$ and $u \in D$.

My question is: for any $d \geq 2n/3$, must such a graph have a dominating set of size $d$? I suspect this is true, but I'm not sure how to prove it.

Answer 1

I assume you are talking about loopless digraphs. (Otherwise there are trivial counterexamples: take a digraph with a loop $vv$ at each vertex $v$ and no other edges; the only dominating set is the whole vertex set $V.$)

Suppose $G$ has $n$ edges, $n\ge2.$ Let $u_1v_1,u_2v_2,\dots,u_mv_m$ be a maximal set of disjoint edges, and let $w_1,w_2,\dots,w_{n-2m}$ be the remaining vertices of $G.$ For each index $i\in\{1,\dots,n-2m\}$ we can choose an index $j_i\in\{1,\dots,m\}$ such that either $u_{j_i}w_i\in E$ or $v_{j_i}w_i\in E.$ Then the set $D=\{u_1,\dots,u_m\}\cup\{v_{j_1},\dots,v_{j_{n-2m}}\}$ is a dominating set of size $d=|D|.$

Case 1. If $n-2m\le m$ then $d\le m+(n-2m)=n-m\le n-\frac n3=\frac{2n}3.$

Case 2. If $n-2m\ge m$ then $d\le2m\le\frac{2n}3.$

In either case we have $d\le\frac{2n}3.$

Answer 2

We induct on $n$. For $n=1$, the claim is vacuously true because there are no directed graphs on $1$ vertex with this property; that can be our base case.

Choose a vertex $v$ with out-degree at least $1$ (such a vertex must exist, because all vertices have in-degree at least $1$) and construct the breadth-first-search tree $T$ of all vertices that can be reached from $v$.

First, I claim that we can find a dominating set for $T$ of size at most $\frac23 |T|$. If $|T|=2$, then $\{v\}$ is a dominating set for $T$ that works. If $|T|=3$, there are two sets that are definitely dominating sets of $T$:

1. $\{v\}$, together with all vertices reached in an even number of steps from $v$.
2. $\{v\}$, together with all vertices reached in an odd number of steps from $v$.

The sum of their sizes is $|T|+1$, since both include $v$ and split the other vertices between them, so one of them has size at most $\frac{|T|+1}{2} \le \frac23 |T|$.

Second, I claim that if we remove $T$ from the graph $G$, then every vertex of the remaining graph still has in-degree at least $1$. If $w$ is a vertex of $G$ not in $T$, and $x$ is some vertex of $G$ with an edge $(x,w)$, then $x$ is not in $T$ - or else we'd have added $w$ to $T$ as well. So every vertex of $G-T$ still has an edge into it from another vertex of $G-T$.

By the inductive hypothesis, $G-T$ has a dominating set of size at most $\frac23(n - |T|)$. Together with the dominating set for $T$ of size at most $\frac23|T|$, we end up getting a dominating set of size at most $\frac23 n$ for all of $G$.