If a set of vertex $X$ is maximal independent, then $X$ is a minimal dominating set

209 Views Asked by At

Attempt:
Suppose $X$ is maximal independent, and then suppose $X$ is not minimal dominating set so that subtracting some vertex(s) will not change its dominating property. But when subtracted, it is no longer maximal independent since its cardinality is reduced by one. Thus Contradiction.

I feel like im missing something in this proof.

1

There are 1 best solutions below

0
On

The correct proof is presented as follows.

Suppose that $X$ is an MIS and is not an MDS. Thus, there is at least one vertex $v$ that can be removed from $X$'s set and convert $X$'s set to a valid MDS.

$v$ has a special character that there exists at least one vertex $u\in N(v)$ that $u\in X$. If $v$ does not have this special character, it can not be removed from $X$. There is a contradiction, for $v$ and $u$ are neighbors, both of them are $\in X$, and $X$ is an MIS.