In graph theory, a dominating set for a graph G = (V, E) is a subset...

Transcribed Image Text:

In graph theory, a dominating set for a graph G = (V, E) is a subset D of V such that every vertex not in D is adjacent to at least one member of D. The domination number v(G) is the number of vertices in a smallest dominating set for G. The dominating set problem concerns testing whether v(G) ≤ K for a given graph G and input K. Prove that the dominating set problem is NP-complete via a polynomial reduction from vertex cover problem to it. In graph theory, a dominating set for a graph G = (V, E) is a subset D of V such that every vertex not in D is adjacent to at least one member of D. The domination number v(G) is the number of vertices in a smallest dominating set for G. The dominating set problem concerns testing whether v(G) ≤ K for a given graph G and input K. Prove that the dominating set problem is NP-complete via a polynomial reduction from vertex cover problem to it.

Answer rating: 100% (QA)

Answer Take the graph G V E with V ab and E Then iG V 2 edit For a nontrivial example c... View the full answer