Ytukyg

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

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