Is the maximal irredundant set a dominating set?

Question

$W$ is irredundant in G=(V,E) if $\ \forall v \in W,\ N[v] - N[W - \{v\}] \not= \emptyset $

But this means maximal irredundant set is a dominating set!

Proof: suppose not then take $W$ a maximal irredundant set: $N[W] \not= V$ then $\exists $u$ \in (V - W) \ s.t. \ N[u] - N[W ] \not= \emptyset $. Contradiction.

With that the irredundant number (which is the cardinality of a minimum maximal irredundant set) denoted by $ir(G)$ equals the domination number $γ(G)$. Where's the mistake?

---

The definition is from the Handbook of Graph Theory by Jonathan Gross and Jay Yellen. Similar definitions are found all over the internet.

Answer 1

There exist maximal irredundant sets which are not dominating sets.

For example, let $G$ be a $5$-cycle with vertices $v_1, v_2, v_3, v_4, v_5$ adjacent (cyclically) in that order. Then $\{v_1, v_2\}$ is a maximal irredundant set, even though it is not dominating, because:

• $\{v_1, v_2, v_3\}$ is not irredundant: $v_2$ is a redundant vertex.
• $\{v_1, v_2, v_5\}$ is not irredundant: $v_1$ is a redundant vertex.
• $\{v_1, v_2, v_4\}$ is not irredundant - this is the surprising case! Here, $v_1$ is redundant, because $\{v_2, v_4\}$ is a dominating set, and in particular $N[\{v_2,v_4\}]$ contains $N[v_1]$. Also, $v_2$ is redundant for similar reasons.
• Then, of course, no superset of any of these three sets can be irredundant.

In general, when $W$ is an irredundant set and $u \notin N[W]$, then $u$ is definitely not going to be redundant in $W \cup \{u\}$, sure - but that doesn't mean that $W \cup \{u\}$ is an irredundant set! Some vertices of $W$ may become redundant with the addition of $u$.

---

Here is an example of a graph $G$ in which $ir(G) \ne \gamma(G)$:

In this graph, the two vertices of degree $3$ form a maximal irredundant set, so $ir(G) =2$, but there is no dominating set of size $2$, and $\gamma(G) = 3$.