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.



Get every new post delivered to your Inbox.

Join 412 other followers