<p>Since there is no single minimal dominating set nor minimal vertex cover, I interpret your question as: </p>

<blockquote>
  <p>There exist one minimal dominating set $D$ and one minimal vertex cover $C$ such that $D \subseteq C$. </p>
</blockquote>

<p>No. </p>

<p>If by <em>any graph</em> you also consider non-connected graphs, then you have a trivial counterexample in $G=(V,E)$ with $V\neq\emptyset$ and $E=\emptyset$, 
i.e. at least one vertex and no edges. 
The minimal vertex cover is $C=\emptyset$, since there are no edges to cover, 
but the only dominating set is $D=V$, and clearly $D\not\subseteq C$.</p>

<p>Even if you restrict it to connected graphs, the answer is still no. Consider the <strong>cycle</strong> graph $G=(V,E)$ of six vertexes $V=\{a,b,c,d,e,f\}$ and $E=\{(a,b), (b,c), (c,d), (d,e),(e,f),(a,f)\}$. </p>

<ul>
<li>The vertex cover sets of minimal size have three elements, obtained by skipping one vertex in two: $\{a,c,e\}$ and $\{b,d,f\}$. </li>
<li>The dominating sets of minimal size are obtained with opposing vertexes, $\{a,d\}$, $\{b,e\}$, and $\{c,f\}$. </li>
</ul>

<p>None of the dominating sets is a subset of any vertex cover set. </p>

CC BY-SA 3.0
2013-07-10T18:17:06.307Z
Your edge set $E$ describes a cycle, not a wheel.
Austin Buchanan
CC BY-SA 3.0
2013-07-11T05:57:51.853Z
I interpret a minimal dominating set as a set $S$ that is a dominating set, and is such that no non-trivial subset of $S$ is a dominating set. In this sense, for connected graphs, any minimal vertex cover is a dominating set, and therefore always contains a minimal dominating set. I would think that your example is more about dominating sets and vertex covers of _minimum_ size.
Neeldhara
CC BY-SA 3.0
2013-07-10T18:09:45.880Z
2013-07-10T18:24:24.993Z
2013-07-10T18:24:24.993Z
Diego Alonso
<p>I interpret your question as follows:</p>

<blockquote>
  <p>Let $M$ be a minimal dominating set (MDS). Then there exists a minimal vertex cover (MVC) $C$ such that $M \subseteq C$.</p>
</blockquote>

<p>The answer is negative. Consider the line
$a - b - c - d$ and the MDS $M=\{a,d\}$. The edge $(b,c)$ isn't covered so either $b$ or $c$ need to be added to $M$ to yield an MVC. However, minimality requires that we then need to remove either $a$ or $d$.</p>

CC BY-SA 3.0
2013-07-10T18:17:02.353Z
2013-07-10T18:17:02.353Z
Peter
<p>I wonder if the minimal dominating set is always a subset of the minimal vertex cover in any graph. If so, what's the proof?</p>

<graph-theory><co.combinatorics><set-theory>
What's the relation between the dominating set and vertex cover?
Yob
# What's the relation between the dominating set and vertex cover?

(Asked by: username_0 on 2013-07-10)

I wonder if the minimal dominating set is always a subset of the minimal vertex cover in any graph. If so, what's the proof?

**Tags:** graph-theory, co.combinatorics, set-theory


---

## 2 answers

### Answer by username_1 on 2013-07-10. Score: 4 | Accepted answer

Since there is no single minimal dominating set nor minimal vertex cover, I interpret your question as:

> There exist one minimal dominating set $D$ and one minimal vertex cover $C$ such that $D \subseteq C$.

No.

If by *any graph* you also consider non-connected graphs, then you have a trivial counterexample in $G=(V,E)$ with $V\neq\emptyset$ and $E=\emptyset$,
i.e. at least one vertex and no edges.
The minimal vertex cover is $C=\emptyset$, since there are no edges to cover,
but the only dominating set is $D=V$, and clearly $D\not\subseteq C$.

Even if you restrict it to connected graphs, the answer is still no. Consider the **cycle** graph $G=(V,E)$ of six vertexes $V=\{a,b,c,d,e,f\}$ and $E=\{(a,b), (b,c), (c,d), (d,e),(e,f),(a,f)\}$.

* The vertex cover sets of minimal size have three elements, obtained by skipping one vertex in two: $\{a,c,e\}$ and $\{b,d,f\}$.
* The dominating sets of minimal size are obtained with opposing vertexes, $\{a,d\}$, $\{b,e\}$, and $\{c,f\}$.

None of the dominating sets is a subset of any vertex cover set.

> **Comments:**
> **username_2**: Your edge set $E$ describes a cycle, not a wheel.  
> **username_3**: I interpret a minimal dominating set as a set $S$ that is a dominating set, and is such that no non-trivial subset of $S$ is a dominating set. In this sense, for connected graphs, any minimal vertex cover is a dominating set, and therefore always contains a minimal dominating set. I would think that your example is more about dominating sets and vertex covers of _minimum_ size.  

---

### Answer by username_4 on 2013-07-10. Score: 4

I interpret your question as follows:

> Let $M$ be a minimal dominating set (MDS). Then there exists a minimal vertex cover (MVC) $C$ such that $M \subseteq C$.

The answer is negative. Consider the line
$a - b - c - d$ and the MDS $M=\{a,d\}$. The edge $(b,c)$ isn't covered so either $b$ or $c$ need to be added to $M$ to yield an MVC. However, minimality requires that we then need to remove either $a$ or $d$.


---

