|
|
|
|
independent set and independence number
|
(Definition)
|
|
|
A set of vertices in a graph  is called an independent set if there are no edges between the vertices.
The independence number of a graph  , usually denoted by  , is the size of a maximal independent set in  .
 means that there are  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)
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 4561 times total.
Classification:
| AMS MSC: | 05C69 (Combinatorics :: Graph theory :: Dominating sets, independent sets, cliques) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
