# A Brief Summary of Independent Set in Graph Theory

**Posted:**April 24, 2010

**Filed under:**Research |

**Tags:**coloring problem, dominating set, graph, graph coloring, independent set, maximal independent set, maximum independent set, mis 1 Comment

### Graph Basics

Let *G* be a undirected graph. *G=(V,E)*, where *V* is a set of vertices and *E* is a set of edges. Every edge *e *in* E *consists of two vertices in *V *of* G. *It is said to connect, join, or link the two vertices (or end points).

### Independent Set

An independent set *S* is a subset of *V* in *G* such that no two vertices in *S* are adjacent. I suppose that its name is meaning that vertices in an independent set *S* is independent on a set of edges in a graph *G*. Like other vertex sets in graph theory, independent set has maximal and maximum sets as follows:

The independent set

Sisis not a proper subset of any independent set ofmaximalif SG.

The independent set

Sisif there is no other independent set has more vertices thanmaximumS.

That is, a largest maximal independent set is called a maximum independent set. The maximum independent set problem is an NP-hard optimization problem.

All graphs has independent sets. For a graph *G* having a maximum independent set, the independence number *α*(*G*) is determined by the cardinality of a maximum independent set.

**Relations to Dominating Sets**

- A dominating set in a graph
*G*is a subset*D*of*V*such that every vertex not in*D*is joined to at least one member of*D*by some edge. - In other words, a vertex set
*D*is a dominating set in*G*if and if only every vertex in a graph*G*is contained in (or is adjacent to) a vertex in*D.* - Every maximal independent set
*S*of vertices in a simple graph*G*has the property that every vertex of the graph either is contained in*S*or is adjacent to a vertex in*S*.- That is, an independent set is a dominating set if and if only it is a maximal independent set.

### Relations to Graph Coloring

- Independent set problem is related to coloring problem since vertices in an independent set can have the same color.

### References

- Chapter 10, Graph Theory: Modeling, Applications, and Algorithms
- http://en.wikipedia.org/wiki/Independent_set_(graph_theory)
- http://en.wikipedia.org/wiki/Dominating_set

Hyunsik Choi: A Brief Summary of Independent Set in Graph Theory http://bit.ly/adIK2G