R igraph manual pages

Use this if you are using igraph from R

Independent vertex sets

Description

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

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.

Author(s)

Tamas Nepusz ntamas@gmail.com ported it from the Very Nauty Graph Library by Keith Briggs (http://keithbriggs.info/) and Gabor Csardi csardi.gabor@gmail.com wrote the R interface and this manual page.

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.

`cliques`

Examples

```
# 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)[])

length(maximal_ivs(g))

## End(Not run)
```

[Package igraph version 1.2.4.1 Index]