# ivs

##### 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

`ivs(graph, min = NULL, max = NULL)`

##### 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

`ivs`

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

and `max`

arguments.

`largest_ivs`

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_ivs`

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

`ivs`

,
`largest_ivs`

and
`maximal_ivs`

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

`ivs_size`

returns an integer constant.

##### 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

```
# NOT RUN {
# Do not run, takes a couple of seconds
# }
# NOT RUN {
# A quite dense graph
set.seed(42)
g <- sample_gnp(100, 0.9)
ivs_size(g)
ivs(g, min=ivs_size(g))
largest_ivs(g)
# Empty graph
induced_subgraph(g, largest_ivs(g)[[1]])
length(maximal_ivs(g))
# }
```

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