igraph-help
[Top][All Lists]

## Re: [igraph] maximal.independent.vertex.sets

 From: Tamas Nepusz Subject: Re: [igraph] maximal.independent.vertex.sets Date: Tue, 7 Apr 2009 16:35:31 +0100

Not sure if anyone here can answer this question, but is the notion of a maximal independent vertex set as generated by maximal.independent.vertex.sets(graph) in igraph the same as the 'maximum independent set' as found in Vanetik, Shimony, and Gudes paper
As I see, yes, it is the same. The concept of independent vertex set is fairly well-established in graph theory, it is practically a set of vertices that are not connected by a single edge at all. Note, however, that there is a difference between the _maximal_ independent vertex sets and the _largest_ (or _maximum_) independent vertex sets, the latter is a subset of the former. A maximal independent vertex set is an independent vertex set that is not contained by any other independent vertex set; a largest independent vertex set is a maximal independent vertex set such that no other independent vertex set contains more vertices. It is easy to select the largest independent vertex sets from the maximal ones, you simply have to keep only those that contain the most vertices.
```
--
Tamas

```