Awesome q2a theme
0 votes
14 views
Please explain the basic difference between Independent set and Dominating Set?
in Graph Theory by (5 points) | 14 views

1 Answer

0 votes

Independent Set: 

So imagine you have a set of vertices, say, V of the given graph. Now to get an independent set, you have to choose some vertices from the given set of vertices, V, such that: 
1. No two vertices are adjacent to each other 
2. Each vertex is only one end point of any edge of the given graph.

There can be many independent sets of a single given graph. 

Example: 

Independent Set - Tutorial And Example

So in this graph:

V = { a, b, c, d, e, f, g, h}

Now lets choose some vertices which satisfy the above criteria: 

  1. {a,c} – This is an independent set as both are non-adjacent and each vertex is only one end point of an edge. 
  2. {a} – A single vertex also forms an independent set. 
  3. {a,g,e,c} – This is a maximal independent set because it is the maximum number of non-adjacent vertices which you can take in the set at a time and also see every vertex is the set touches some edges and all the edges in this way are covered here. Vertex a for edges ab and ad. Vertex g for edges dg and gb. Vertex e for edges de, be, eh and ef. Vertex c for edges bc, ch and cf. Hence all the edges are covered. 
  4. Here independence number become 4. 

The aim here is to find maximal independent set. 

Dominating Set:

Again let’s say you have the same set of vertices, V. Now what makes a dominating set is: 

  1. It is a subset of V, say V’, such that upon choosing any random vertex from V, either that is present in V’ or at least its adjacent vertex is present in V’. 
  2. Vertices can be adjacent or non-adjacent here. It doesn’t matter.

Again there can be many dominating sets for a graph. 

Example: 

Independent Set - Tutorial And Example

So we will find the dominating set for the same graph: V = {a,b,c,d,e,f,g,h}

  1. {a,b,c,d,e,f,g,h} – all the vertices will make a dominating set. 
  2. But the aim here is to find a minimal dominating set. 
  3. {a, b, c} – It is a minimal dominating set. So the definition says when you choose any vertex randomly from V, either it should be present in our dominating set or at least its adjacent should be present. So take vertex a – vertex a is present in dominating set. Now choose b or c, see both are present in the dominating set. Now lets choose d, though d is not present but its adjacent a is present. Similarly take g or even e, both are not present but their adjacent vertex b is there. Likewise for h and f vertices, their adjacent vertex c is present in the set. So we get a minimal dominating set covering all the vertices. 
  4. Here domination number becomes 3. 

Major differences between independent and dominating set:

First of all the difference between maximal and maximum is maximal means you cannot add anything more to the set, if you do so then it will violate the conditions. And maximum means greatest maximal independent set which gives you the independence number. Similarly minimal means you can’t remove anything from it and smallest minimal dominating set gives you the domination number.
  1. Domination number <= Independence number
  2. Every independent set is a dominating set but not vice versa.
  3. Only non-adjacent vertices are considered in independent set but anything is okay with dominating set.

 

ago by (-20 points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
Welcome to GATE CSE Doubts, where you can ask questions and receive answers from other members of the community.
9,105 questions
3,156 answers
14,594 comments
95,955 users