maximum independent set

• 2019 Sorge2019
  • page 11 : clique cover number $k$ upper bounds maximum independent set by $\mathcal O(k)$ – Lemma 4.26. The minimum clique cover number $c$ strictly upper bounds the independence number $\alpha$.
• unknown
  • maximum independent set $k$ upper bounds domination number by $\mathcal O(k)$ – Every maximal independent set is also a dominating set because any undominated vertex could be added to the independent set.
  • maximum independent set $k$ upper bounds maximum induced matching by $\mathcal O(k)$ – Each edge of the induced matching can host at one vertex of the independent set.
• 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.