Question

) A vartex cover is n set af vertices for which esch edge has at lesst ane of its vertices in the set. What is the size of the smallest vertex ㏄ver in the Petersen graph? Give an example of such a set Prove that a smaller set does not exist. A dominating sot is a set of vertices for which all other vertices have nt lenst ane neighbar in this set. What is the e of the smallest dominating set in the Petersen gruph? Give an exmple af such n set. h) Prove that a smaller set does not exist.

Answer 1

A vertex cover of a graph G is a subset of vertices S $\subseteq$ V (G) such that every edge has an endpoint in S. (That is, for all e $\in$ E(G), $e \bigcap S \neq \emptyset$ )

a 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.

e.

Vertices clored yellow from a vertex cover.

Petersen graph β(G-6

f.

Prove by contradiction. Suppose there exists a vertex cover of < 6 vertices. Now, given any 5 vertices of a graph then at maximum they can cover 5C2 = 10 edges. But there are 15 edges in Petersen Graph. Thus, no vertex cover of size <= 5 can be valid. Thus, 6 is the minimum size of vertex cover.

g.

Vertices in red form a dominating set.

h.

Proof by contradiction. Let there be dominating set of size 2. Now since every vertex in petersen graph has degree 3, so these 2 vertices in dominating set can have 2*3 = 6 neighbours combined. Now, 6 + 2 = 8 which is less then the number of vertices in Petersen graph ( which are 10). So, the above dominating set with 3 vertices is the minimum possible.