Vertex Cover, Domination

Def: Menge M $\subseteq$ V heißt Knotenüberdeckung (vertex cover) von G = (V, E), falls $\forall$xy $\in$ E : x $\in$ M $\vee$ y $\in$ M.

Vorsicht: Es werden Kanten überdeckt (durch Knoten). Nicht verwechseln mit:

Def: Menge M $\subseteq$ V heißt dominierende Menge von G, falls M $\cup$ G(M) = V.

Aufgabe: Finde G, bei denen Größe eines kleinsten vertex cover $\neq$ Größe einer kleinsten dominierenden Menge.