maximum independent set

equivalent to: maximum independent set

providers: ISGCI

Relations

Results

• 2019 The Graph Parameter Hierarchy by Sorge
  • 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$.
• 1988 The average distanceisnot morethan the independence number by Chung
  • maximum independent set upper bounds average distance by a linear function – [ed. paraphrased from another source] Let $G$ be a graph. Then $\bar{D} \le \alpha$, with equality holding if and only if $G$ is complete.
• 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.
• assumed
  • maximum independent set upper bounds bipartite number by a linear function – folklore
• 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.