Independent set
Definition
Let be a graph. An independent set in is a set of vertices of such that no two vertices of are adjacent.
Remarks
A set is independent in if and only if it is a clique in the complement graph. A set is independent if and only if its complement in the vertex set is a vertex cover. The largest size of an independent set is the independence number . Each colour class of a colouring is an independent set.
Further reading
About this page
| Tag | 0KZJ82WEPP |
|---|---|
| URI | m2://0KZJ82WEPP |
| Kind | definition |
| Writing | W1 stated |
| MSC | 05C69 |
| Defines | Independent set |
Markdown · JSON · Edit on GitHub
What this page needs for W2
- edge instance_of in: one example (0 of 1)
- edge not_instance_of in: one non-example that fails one clause (0 of 1)
The writing levels say how complete the text of a page is. They do not measure its truth.
What links here
No page links to this page yet.