# independent.vertex.sets

##### Independent vertex sets

A vertex set is called independent if there no edges between any two vertices in it. These functions find independent vertex sets in undirected graphs

- Keywords
- graphs

##### Usage

```
independent.vertex.sets(graph, min=NULL, max=NULL)
largest.independent.vertex.sets(graph)
maximal.independent.vertex.sets(graph)
independence.number(graph)
```

##### Arguments

- graph
- The input graph, directed graphs are considered as undirected, loop edges and multiple edges are ignored.
- min
- Numeric constant, limit for the minimum size of the
independent vertex sets to find.
`NULL`

means no limit. - max
- Numeric constant, limit for the maximum size of
the independent vertex sets to find.
`NULL`

means no limit.

##### Details

`independent.vertex.sets`

finds all independent vertex sets in
the network, obeying the size limitations given in the `min`

and
`max`

arguments.

`largest.independent.vertex.sets`

finds the largest independent
vertex sets in the graph. An independent vertex set is largest if
there is no independent vertex set with more vertices.

`maximal.independent.vertex.sets`

finds the maximal independent
vertex sets in the graph. An independent vertex set is maximal if it
cannot be extended to a larger independent vertex set. The largest
independent vertex sets are maximal, but the opposite is not always
true.

`independece.number`

calculate the size of the largest
independent vertex set(s).

These functions use the algorithm described by Tsukiyama et al., see reference below.

##### Value

`independent.vertex.sets`

,`largest.independent.vertex.sets`

and`maximal.independent.vertex.sets`

return a list containing numeric vertex ids, each list element is an independent vertex set.`independence.number`

returns an integer constant.

##### concept

Independent vertex set

##### References

S. Tsukiyama, M. Ide, H. Ariyoshi and I. Shirawaka. A new algorithm
for generating all the maximal independent sets. *SIAM J Computing*,
6:505--517, 1977.

##### See Also

##### Examples

```
# A quite dense graph
g <- erdos.renyi.game(100, 0.8)
independence.number(g)
independent.vertex.sets(g, min=independence.number(g))
largest.independent.vertex.sets(g)
# Empty graph
induced.subgraph(g, largest.independent.vertex.sets(g)[[1]])
length(maximal.independent.vertex.sets(g))
```

*Documentation reproduced from package igraph, version 0.6.5-2, License: GPL (>= 2)*