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$

2 Answers 2

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.

$\endgroup$
2
  • 1
    $\begingroup$ Your edge set $E$ describes a cycle, not a wheel. $\endgroup$ Commented Jul 10, 2013 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
    Commented Jul 11, 2013 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$.

$\endgroup$
0

Your Answer

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

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