maximum independent set

• Sorge2019
  • page 11 : clique cover number upper bounds maximum independent set by a linear function – Lemma 4.26. The minimum clique cover number $c$ strictly upper bounds the independence number $\alpha$.
• https://en.wikipedia.org/wiki/Maximal_independent_set
  • maximum independent set – For a graph $G=(V,E)$, an independent set $S$ is a maximal independent set if for $v \in V$, one of the following is true: 1) $v \in S$ 2), $N(v) \cap S \ne \emptyset$ where $N(v)$ denotes the neighbors of $v$. … the largest maximum independent set of a graph is called a maximum independent set.
• unknown source
  • maximum independent set upper bounds domination number by a linear function – Every maximal independent set is also a dominating set because any undominated vertex could be added to the independent set.
  • maximum independent set upper bounds maximum induced matching by a linear function – Each edge of the induced matching can host at one vertex of the independent set.