3
$\begingroup$

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.

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

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
1
  • 5
    $\begingroup$ 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. $\endgroup$ Commented Jan 6, 2023 at 20:56
1
$\begingroup$

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .