|
|
|
|
independent set and independence number
|
(Definition)
|
|
|
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) \geq \nu$ means that there are $\nu$ vertices with no edges between them.
An independent set is sometimes called a stable set or an anticlique.
|
Anyone with an account can edit this entry. Please help improve it!
"independent set and independence number" is owned by rspuzio. [ full author list (2) | owner history (1) ]
|
|
(view preamble | get metadata)
See Also: clique
| Other names: |
stable set, anticlique |
| Also defines: |
independent set, independence number |
|
|
Cross-references: size, edges, graph, vertices
There are 6 references to this entry.
This is version 3 of independent set and independence number, born on 2004-07-27, modified 2006-11-10.
Object id is 6038, canonical name is IndependentSetAndIndependenceNumber.
Accessed 5845 times total.
Classification:
| AMS MSC: | 05C69 (Combinatorics :: Graph theory :: Dominating sets, independent sets, cliques) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
