Vertex cover vs dominating set

Question

I'm trying to understand the difference between vertex cover and dominating set.

From what understand, in dominating set, the set D contains vertices that adjacent to other vertices that are not in D (for every v in V, either v is in D or it is adjacent to one in D).

In vertex cover all the vertices in D cover all the edges, but by doing that they are adjacent to other vertices they are not in D - So why is it not a dominating set?

Solution 1

I found some graphs on Wikipedia's Dominating Set article that illustrate this difference.

These examples show dominating sets (in red) that aren't vertex covers, the opposite of what you asked later on in your question. The edges in (V-D) prevent them from being vertex covers.

Solution 2

Previous answers are good however the simplest example is yet to be written here so:

Solution 3

I was not quickly able to comprehend the difference between vertex cover and dominating set from the given answers, so I looked it up.

Definition Vertex Cover:

According to Wikipedia:

"vertex cover of a graph is a set of vertices that includes at least one endpoint of every edge of the graph."

So in simple words, for every line, 1 of the 2 dots/nodes (connected to the ends of the line), must be in the set of dots/nodes.

Definition Dominating Set:

According to Wikipedia:

dominating set for a graph G = (V, E) is a subset D of V such that every vertex not in D is adjacent to at least one member of D.

So in simple words: all dots/nodes must be in the set (of dots/nodes), or connected to the set with a single line/edge.

Explanation of given example

That is why in the example as given by @Daniel:

Every 2 nodes is a vertex cover, and a single node can't be a vertex cover, because then the line opposed to the chosen node does not have "at least 1 node in the vertex cover set".

Visualisation of difference

The difference is shown in the following figure:

However 1 node is a dominating set, because in that case all nodes are either: in the set, or connected to the set by 1 line. (the 1 line here is distance wise, it could also be perfectly fine if there were 2 lines in parallel connected to the dominating set, as long as it is not just only 2 lines in series/behind eachother, connected to the dominating set).

An example to visualise why a single node is a Dominating set in 3 nodes is added below:

Solution 4

1. A vertex cover may not be a dominating set if you have a degree zero vertex outside your vertex cover. The vertex cover 'covers' all the edges, but the degree zero vertex is not adjacent to the vertex cover.

2. A dominating set may not be a vertex cover if there is an edge, say e = (u,v), where u and v are both outside the dominating set. This is possible, if u and v are both adjacent to vertices in the dominating set by other edges.

Solution 5

You only need to consider a path on four vertices to distinguish the two notions. Let a,b,c,d be consecutive vertices of such a path. Then {a,d} is a dominating set, but not a vertex cover (since it fails to cover the edge bc).

View more solutions

Comments

[Eli4ph]

Maybe not. If the graph contains isolated vertices (zero-degreed vertices), then a dominating set must include these isolated vertices while a vertex cover do not have to include them.