# Coloring of graph such that every vertex in graph is either colored or shares an edge with a colored vertex

I'm a bit of a graph theory noob, so please forgive the absence of mathematical rigor in my question.

Here it is:

Given a graph $G \to (V,E)$, (where every vertex $v$ in $G$ has some weight $w$ associated to it), I am seeking an efficient algorithm that will find a subset $V'$ of the graph with the least total weight such that every vertex $v$ in $G$ satisfies at least one of the following conditions:

1. $v$ is in $V'$
2. $v$ shares at least one edge with some vertex in $V'$

-
It's called a "minimum weighted dominating set". –  Douglas S. Stones Aug 12 '12 at 23:06