Relation between independent and dominating set

2.7k Views Asked by At

I came across this paragraph on wikipedia page:

Dominating sets are closely related to independent sets: an independent set is also a dominating set if and only if it is a maximal independent set, so any maximal independent set in a graph is necessarily also a minimal dominating set. Thus, the smallest maximal independent set is greater or equal in size than the smallest independent dominating set. The independent domination number $i(G)$ of a graph $G$ is the size of the smallest independent dominating set (or, equivalently, the size of the smallest maximal independent set).
The minimum dominating set in a graph will not necessarily be independent, but the size of a minimum dominating set is always less than or equal to the size of a minimum maximal independent set.

I didnt get following

  1. The Second sentence: "Thus, the smallest maximal independent set is greater or equal in size than the smallest independent dominating set."
  2. The last half sentence: "but the size of a minimum dominating set is always less than or equal to the size of a minimum maximal independent set"

Some facts:

  1. Maximal independent set is also minimal dominating (as stated in first line in above paragraphs)
  2. Independent dominating set is also maximal independent as specified here:

    A set of vertices is a maximal independent set if and only if it is an independent dominating set.

Now my doubts:

  1. I believe, due to point 1 and 2 above, we can say,

    Size of maximal independent set
    = Size of minimal independent dominating set

    Adding "smallest" on both sides above, we get

    Size of smallest maximal independent set
    = Size of smallest minimal independent dominating set

    Then the second sentence must be wrong in saying "greater or equal", right?

  2. I understand that minimal dominating sets can be either independent or not-independent. Similarly smallest dominating sets can be either independent or non-independent. I believe in the last half sentence , wikipedia article meant "smallest" by "minimum" (right?). As stated in above point

    Size of smallest maximal independent set
    = Size of smallest minimal independent dominating set

    Adding to this the set of smallest non-independent dominating set makes set of smallest dominating set. Then how is the last half sentence correct in saying "less than or equal"? I guess it should be "greater than or equal", right?

PS: note that smallest set is by fact minimal, so we can very well drop "minimal" following "smallest" and add "minimal" after "smallest" as per convinience.

Edit
I guess, I got it. Need confirmation for below.
I was wrong in saying: "Adding to this the set of smallest non-independent dominating set makes set of smallest dominating set." Smallest dominating set is either smallest independent dominating set or smallest non-independent dominating set, if both have different size. Thus smallest dominating set equals smallest independent dominating set if smallest independent dominating set is smaller than smallest non independent dominating set. Whereas, smallest dominating set is less than smallest independent dominating set if smallest independent dominating set is greater than smallest non independent dominating set, in which case smallest dominating set is equals smallest non independent dominating set.

Am I thinking unnecessarily too much?