# independent.vertex.sets

0th

Percentile

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

cliques

##### Aliases
• independent.vertex.sets
• largest.independent.vertex.sets
• maximal.independent.vertex.sets
• independence.number
##### 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
subgraph(g, largest.independent.vertex.sets(g)[[1]])

length(maximal.independent.vertex.sets(g))
Documentation reproduced from package igraph, version 0.5.5-3, License: GPL (>= 2)

### Community examples

Looks like there are no examples yet.