Let $N(G)$ be the null graph. What's the number of vertex cover for this graph? I wanted to modify the reduction from SAT to vertex cover by adding vertices that are not connect to any vertices.

  • $\begingroup$ You can always remove vertices of degree at most two trivially in vertex cover. Isolated vertices can be removed, the neighbor of a leaf can be removed by decreasing the budget by one. Degree two vertices are left to the reader. $\endgroup$ – Pål GD May 8 '13 at 17:55
  • $\begingroup$ I didn't understand you ! the reduction from 3-SAT to Vertex Cover is described in Sipser book , there he mention that there are in the graph a vertex cover of size $k=n+2m$ while total number of vertices is $2n+3m$ so we have : $l=\frac{k}{2n+3m}$ so I want to increase the number of vertices such that : $l=\frac{n+2m}{2n+4m}=\frac12$ $\endgroup$ – Fayez Abdlrazaq Deab May 8 '13 at 20:08

The minimum vertex cover for a totally disconnected graph is the empty set. A vertex cover is a set of vertices that covers all the edges, i.e. every edge in the graph needs at least one of its endpoints in the vertex cover, so if there are no edges in the graph, no edges need covering.

  • $\begingroup$ A disconnected graph can usually contain edges. $\endgroup$ – Pål GD May 8 '13 at 17:54
  • $\begingroup$ @PalGD: edited to fix that. $\endgroup$ – Niel de Beaudrap May 8 '13 at 19:07
  • $\begingroup$ @NieldeBeaudrap ta. $\endgroup$ – Luke Mathieson May 9 '13 at 0:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.