6 5 4 2 1 3 Dominating Set (DS): For the graph above, select all the correct sta

Question

6 5 4 2 1 3 Dominating Set (DS): For the graph above, select all the correct statements below. Note that incorrect answers are penalized. Select one or more: A. A minimum size of the dominating set in this graph is 2. B. Nodes (3,6) form a dominating set in this graph. C. If I used a greedy heuristic to find a dominating set, I would start with node 6 in this graph. D. Unlike independent set search, my greedy heuristic for the DS would start with the node with the largest number of adjacent nodes (highest degree). E. If DS is a dominating set in graph G, then these nodes must form a clique. FAll of the above. G. Every graph has only ONE minimum dominating set. H. If G (n, m) and there is a node of degree (n-1), then the size of the DS is one. I. If the graph has k-clique, then the DS must include at least one node from this clique.

Explanation / Answer

A ) It is correct because minimum size dominated set is (2,5).

B) No, it not cover all vertices.

C)Yes

D)Yes

Related Questions

Navigate

• Browse (All)
• Browse 6
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.