1
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Your edge set $E$ describes a cycle, not a wheel. $\endgroup$ – Austin Buchanan Jul 10 '13 at 18:17
  • 1
    $\begingroup$ 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. $\endgroup$ – Neeldhara Jul 11 '13 at 5:57
4
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$

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.