3
$\begingroup$

Suppose $G$ is a connected graph and $S$ is a vertex cover. Prove that $S$ is also a dominating set.

Can I get some help with proving this? I know that a dominating set in an undirected graph $G=(V,E)$ is a subset $S$ subset of $V$ such that every vertex is either in $S$ or has a neighbor in $S$.

I know that a vertex cover is always going to be a dominating set because a vertex cover set is such that every edge has a vertex in the set, which means that a vertex not in the set (so on the other end of the edge) must have a neighbor in the set in order for all edges to be covered...

I just don't know how to write this as a proof.

Improve this question
$\endgroup$
2
  • $\begingroup$ The statement is false for 1-vertex graphs, as the empty set is a vertex cover but it doesn't dominate the lone vertex. What very simple property about the degree distribution of vertices does the singleton graph have that no other connected graph possesses? Now use that property. $\endgroup$
    – Yonatan N
    Dec 15, 2018 at 4:26
  • $\begingroup$ Since this question is purely about graph theory (not algorithms), it seems better suited for Math SE. $\endgroup$
    – dkaeae
    Dec 15, 2018 at 8:08

1 Answer 1

Reset to default
1
$\begingroup$

Here is a correct version of your result:

If a graph contains no isolated vertices, then every vertex cover is a dominating set.

For the proof, let $G$ be a graph with no isolated vertices, and let $S$ be a vertex cover. In order to show that $S$ is a dominating set, we need to show that every vertex not in $S$ has a neighbor in $S$. Suppose therefore that $v \notin S$. Since $G$ has no isolated vertices, $v$ has some neighbor $u$. Since $S$ is a vertex cover, it must contain one of $v,u$. Since $v \notin S$, necessarily $u \in S$. Therefore $v$ has a neighbor $u \in S$.

A stronger version of this result states that the condition of having no isolated vertices is tight.

Let us call a graph good if every vertex cover is a dominating set.

A graph is good iff it contains no isolated vertices.

We already saw one direction. Now suppose $G$ is a graph containing some isolated vertex $v$. Take an arbitrary vertex cover $S$. Since $v$ is isolated, $S \setminus \{v\}$ is also a vertex cover, but it is not a dominating set, since $S \setminus \{v\}$ doesn't contain $v$ or any of its neighbors (since it has none!).

Improve this answer
$\endgroup$
4
  • $\begingroup$ I'm not amazing at proof writing, and I feel stupid even asking this, but is the way you've written it then a proof? And if it is, does it count as a specific type of proof? it obviously isn't contradiction; thank you so much! $\endgroup$
    – User9123
    Dec 15, 2018 at 23:57
  • $\begingroup$ I'd say it's a "direct proof", but these terms are useful mostly when just starting out. The only way to understand what constitutes as proof is to read many of them, and to have others critic your own proof attempts. $\endgroup$
    – Yuval Filmus
    Dec 16, 2018 at 0:03
  • $\begingroup$ Is this the same thing as then saying that Dominating-Set <=p Vertex-Cover? At least for a minimum vertex cover? $\endgroup$
    – User9123
    Dec 16, 2018 at 22:15
  • $\begingroup$ Not at all. Polytime reductions are very different from the simple statements proved in my answer. $\endgroup$
    – Yuval Filmus
    Dec 16, 2018 at 22:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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