A Brief Summary of Independent Set in Graph TheoryPosted: 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
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).
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.
- Chapter 10, Graph Theory: Modeling, Applications, and Algorithms