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?
$\begingroup$
$\endgroup$
$\begingroup$
$\endgroup$
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.
answered Jul 10 '13 at 18:09
-
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
$\begingroup$
$\endgroup$
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$.
