Re: Definition of a Maximal Independent Set -> Starting from a Dominating Set


iwan2no@xxxxxxxxxxx wrote:
Hi,

I've got a question about Maximal Independent Set & Dominating Set:

If I say that I've got a subset of nodes V' of set V which:

1. form a dominating set
2. are *not* adjacent to each other

Then would I be correct to state that the subset V' that I've got is
actually a maximal independent set?

Well, can you add a vertex to V' and get another maximal independent
set? If so, that vertex is not adjacent to any vertex in V', which
means V' is not a dominating set after all. So yes, V' is a maximal
independent set.

It is also a minimal dominating set, by a similar argument.

--- Christopher Heckman

I know that given any graph G, any maximal independent set it also a
dominating set. I just want to know if I look at things from the other
direction, i.e. I've got a set that's dominating and none of the
vertices in that set are adjacent, then do I get a maximal independent
set... hope I've managed to explain the question clearly.

Would appreciate any comments.

Cheers,
Sam

.

Quantcast