Talk:Dominating set

From Wikipedia, the free encyclopedia

This article may be too technical for a general audience. Please help improve this article by providing more context and better explanations of technical details to make it more accessible, without removing technical details.

[edit] illustration

I'd quite some trouble seeing the difference between NODE COVE and DOMINATING SET. Its easy to interpret the definition so that they are identical. Thats why I think this article would benefit from some sort of illustration to the problem.83.249.48.221 08:30, 11 December 2006 (UTC)A

[edit] validity

I wonder about the reduction used in the proof. If G is not connected, it fails because vertices V of degree 0 are not required to be members of C, but must be members of C if C is a dominating set of G'. (Trivially: Suppose vertex v of degree 0 is not in the dominating set. Then by definition, it must be joined to a member of the dominating set by an edge. But by definition, v has no incident edges. This is a contradiction; consequently, v must be a member of the dominating set.)

Presumably this could be addressed by defining G'=(V',E) where V' = {all vertices v in V such that degree(v) > 0}?

For that matter, I still have problems with the construction of G' to assist with proving that the existence of a dominating set for G' implies the existence of a vertex cover for G. I can see that having vertex "vw" covered by D implies that edge (v,w) is covered, but how do we ensure D is a proper subset of V (i.e. it does not contain any of the vertices created by the transformation)?

Scott 03:38, 14 April 2007 (UTC)