Pergunta

Suppose $G$ is a connected graph and $S$ is a vertex cover. Prove that $S$ is also a dominating set.

Can I get some help with proving this? I know that a dominating set in an undirected graph $G=(V,E)$ is a subset $S$ subset of $V$ such that every vertex is either in $S$ or has a neighbor in $S$.

I know that a vertex cover is always going to be a dominating set because a vertex cover set is such that every edge has a vertex in the set, which means that a vertex not in the set (so on the other end of the edge) must have a neighbor in the set in order for all edges to be covered...

I just don't know how to write this as a proof.

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top