# Domination number is at most $n/2$

Let $$G$$ be a graph of $$n$$ vertices with no isolated vertex. Prove that the domination number of $$G$$ is at most $$\lfloor n/2 \rfloor.$$

Turns out this result can easily solve a combinatorics problem I'm working on right now. And since the problem only asks for even $$n$$ I'm going to ignore the odd numbers for the moment.

I tried induction like this: The base case is clear so assume the result hold for some even number $$n$$. Now given a graph of $$n+2$$ vertices I want to remove $$2$$ vertices so I can use the induction hypothesis. The problem is that for some graphs, removing any two vertices will give a graph with isolated vertices.

• Induction on vertices won't work for precisely this reason. Commented Jan 6, 2023 at 20:05

Let $$V$$ denote the set of vertices of the graph $$G$$, let $$D \subseteq V$$ denote a dominating set, and let $$N = V - D$$ be the set of neighboring vertices. Also, put $$n = |V|$$. We can establish your result with the following two claims. Try to write down proofs before revealing them.

Claim: Either $$|D| \leq \lfloor \frac{n}{2} \rfloor$$ or $$|N| \leq \lfloor \frac{n}{2} \rfloor$$.

Proof: If both $$|D|$$ and $$|N|$$ are greater than $$\lfloor \frac{n}{2} \rfloor$$, then $$n = |V| = |D| + |N| \geq \bigl(1 + \lfloor \tfrac{n}{2} \rfloor \bigr) + \bigl(1 + \lfloor \tfrac{n}{2} \rfloor \bigr) > n,$$ a contradiction.

Now, the dominating number $$\gamma(G)$$ is the minimum $$|D|$$ over all dominating sets $$D \subseteq V$$, so in order to prove the claim, we have to guarantee that there exists some dominating set $$D$$ with $$|D| \leq \lfloor \frac{n}{2} \rfloor$$. The trick is symmetry:

Claim: If $$(D, N)$$ is a pair consisting of a dominating set and its neighbors, then so is $$(N, D)$$.

Proof: Since $$V = D \sqcup N$$, every vertex is in exactly one of the two sets. The relation on vertices of being neighbors is symmetric: if $$v$$ and $$w$$ share an edge, then the same can be said about $$w$$ and $$v$$. Therefore, from the perspective of $$N$$, every vertex is either in $$N$$ or is a neighbor in $$D$$. Hence, $$N$$ is a dominating set for $$G$$.

Together, the two claims demonstrate that at least one of $$D$$ or $$N$$ is a dominating set of size no more than $$\lfloor \frac{n}{2} \rfloor$$, as desired.

• The second claim does not hold unless $D$ is a minimal dominating set; for a counterexample otherwise, take $D$ to be all of $V$ and $N = \varnothing$. If $D$ is minimal, it does hold, assuming that there are no isolated vertices, but the proof does need to use both of those assumptions! In the end, this is fine, because we can assume $D$ is a minimal dominating set, and we are given that there are no isolated vertices. Commented Jan 6, 2023 at 20:56

Another similar proof:

1. Show that for any graphs (even with isolated vertices) there exists an independent dominating set.
2. Show that if $$X$$ is an independent dominating set, then $$\overline{X}$$ is a dominating set.
3. Conclude that either $$X$$ either $$\overline{X}$$ has the desired size where $$X$$ is an independent dominating set.

Proofs:

1. By induction on the number of vertices. Consider a vertex v. By induction there exists an independent dominating set $$X$$ of $$G \setminus N[v]$$ (where $$N[v]$$ denotes the closed neighborhood). Thus $$X \cup \{v\}$$ is an independent dominating set of $$G$$.
2. Consider $$X$$ an independent dominating set of $$G$$. Let $$x$$ be a vertex of $$X$$, as $$x$$ is not isolated, $$x$$ has a neighbor called $$y$$. As $$X$$ is an independent set, then $$y \not\in X$$. Thus $$y \in \overline{X}$$ dominates $$x$$. We conclude that $$\overline{X}$$ is a dominating set of $$G$$.
3. As $$V(G) = X \cup \overline{X}$$ and as the union is disjoint, then $$n = |X| + |\overline{X}|$$. We deduce that $$|X| \geq n/2$$ or $$|\overline{X}| \geq n/2$$.