2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.$

$\endgroup$
0
1
$\begingroup$

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$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.