91Ó°ÊÓ

The vertex Cover problem for an undirected graph$G(V,E)$ , is said to be$S⊆V$ vertex cover, if and only if any edge of graph G is adjacent to at least one vertex in S. It is NP-complete problem.

Any vertex cover problem is reduced to the dominating set problem

Consider an undirected graph G, for any side uv of the graph G , add a point t so that the two vertices u and v of the side are in phase with t respectively. Get a new undirected graph G'.

If the original undirected G graph has a vertex cover S , and S satisfies$\left|S\right|≤b$ , then can also be used as a dominating set of graphs G' that satisfies the conditions.

Assume is not the dominating set of the graph G', that is, there is a point $t∈V\left(G^{\text{'}}\right)$so that $t∉S$and t is not adjacent to any vertex in s . Since the graph g is connected, there must be edges (u,t) satisfying $u∉S$.

The edge ( u,t ) bis an auxiliary edge added to the original graph.

When the edge corresponding to $t$is $\left(u,v\right)$, is a cover of G, and the vertex u of the $\left(u,v\right)$edge does not belong to$S$, then vertex $v$must belong to $S$.

If is adjacent to$v$ , then it $S$is proved that if is a vertex cover of the undirected graph$G$, and $\left|S\right|≤b$, then$S$ is the dominating set of the graph$G\text{'}$ .

Therefore, any vertex cover problem can be reduced to the dominance set problem.