1
$\begingroup$

Let $D$ be a minimal dominating set in $G$ ($|D| = \gamma(G)$). Then by definition, we know that for every $x \in V(G) \setminus D$, there exists $y \in D$ such that $xy \in E(G)$. Then I denoted by $P$ the set of these $|V(G)| - |D|$ edges in $G$. In a few examples, I now see that $P$ could be an edge cover in $G$, but I don't know how to even start proving this in general (I haven't yet used the fact that $D$ is minimal, which means that for every $x \in D$, $D \setminus $ {$x$} is not a dominating set in $G$). How should I then put this all together into a proof?

$\endgroup$

1 Answer 1

1
$\begingroup$

You need to assume that there are no isolated vertices for there to be an edge cover. Your approach looks good. Try arguing by contradiction. You need to prove that every vertex is incident with an edge in $P$. For each vertex, either it belongs to $D$ or its complement. The case you are missing is the first. Suppose $v \in D$ and $v$ is not incident with any edge in $P$. Show that $D - x$ is a dominating set.

$\endgroup$
6
  • $\begingroup$ So now I need to prove that for every $y\in V(G)−(D−${$x$}), there exists $z\in D-$ {$x$} such that $yz\in E(G)$. I know that for every $x\in V(G)−D$, there exists $y\in D$ such that $xy\in E(G)$. So I need to prove that for $x$ there exists $z\in D-$ {$x$} such that $xz\in E(G)$. How can I do it? $\endgroup$
    – good12
    May 15 at 19:19
  • $\begingroup$ I think will be simpler to think about it this way: if $D-x$ were not a dominating set, then what type of vertex must be adjacent to $x$? $\endgroup$ May 16 at 11:21
  • $\begingroup$ I don’t know what type. $\endgroup$
    – good12
    May 16 at 11:25
  • $\begingroup$ It's the type that is not incident with any edge in $P$. So, will $D$ still be a vertex dominating set when you remove $x$ from it? $\endgroup$ May 16 at 11:31
  • 1
    $\begingroup$ If $x \in D$ is not incident with any edge of $P$ and we are assuming there are no isolated vertices, then all of the neighbors of $x$ belong to $D$. Therefore, if you remove $x$, what remains is still a vertex domination set. So, if you started with a minimal dominating set set and there were such an $x$, then we will have found a contradiction. Therefore, the set $P$ you defined is an edge cover when $D$ is a minimal vertex domination set and $G$ has no isolated vertices. $\endgroup$ May 17 at 13:18

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .