Talk:Dominating set problem

From Wikipedia, the free encyclopedia

The language of this page needs to be cleaned up, especially the section containing the reduction from vertex cover. I removed some minor spelling and grammatical errors, but amost the whole section needs to be rewritten. The content seems OK. DVanDyck 13:31, 13 September 2006 (UTC)

[edit] Disconnected graph

I'd appreciate if someone could explain why this is not a counter-example: a graph with two vertices, A and B, and no edge between them. There's a vertex cover of size 0, namely the empty set. The reduction described is idempotent on this graph (there are no edges, so no new vertices or edges are added). However, there is no dominating set of size 0; the smallest dominating set is {A,B}, i.e., of size 2. 76.182.204.23 05:16, 26 March 2007 (UTC)

[edit] Disconnected graph

The problem asks for a positive integer k. 0 is nonnegative but not positive. 71.121.137.70 06:16, 25 May 2007 (UTC)Zrflx

[edit] incomplete proof

I think the proof is not quite correct.

(\Rightarrow) D is a dominating set of size k in G '. So, every edge hits some vertex in D. D is a vertex cover in G of size k.

This is not true, because not all vertices in D are vertices in G. You have to "move" them to adjacent G-vertices first. --129.59.223.115 20:10, 20 June 2007 (UTC)