A Brief Summary of Independent Set in Graph Theory

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 S is maximal if S is not a proper subset of any independent set of G.

The independent set S is maximum if there is no other independent set has more vertices than S.

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