independent set and independence number

A set of vertices in a graph $G$ is called an independent set if there are no edges between the vertices.

The independence number of a graph $G$, usually denoted by $\alpha (G)$, is the size of a maximal independent set in $G$. $\alpha (G)\ge \nu$ means that there are $\nu$ vertices with no edges between them.

An independent set is sometimes called a stable set or an anticlique.

Title	independent set and independence number
Canonical name	IndependentSetAndIndependenceNumber
Date of creation	2013-03-22 14:30:06
Last modified on	2013-03-22 14:30:06
Owner	rspuzio (6075)
Last modified by	rspuzio (6075)
Numerical id	6
Author	rspuzio (6075)
Entry type	Definition
Classification	msc 05C69
Synonym	stable set
Synonym	anticlique
Related topic	Clique2
Defines	independent set
Defines	independence number