StudySmarter AI is coming soon!

- :00Days
- :00Hours
- :00Mins
- 00Seconds

A new era for learning is coming soonSign up for free

Suggested languages for you:

Americas

Europe

Q23SE

Expert-verifiedFound in: Page 738

Book edition
7th

Author(s)
Kenneth H. Rosen

Pages
808 pages

ISBN
9780073383095

**A dominating set of vertices in a simple graph is a set of vertices such that every other vertex is adjacent to at least one vertex of this set. A dominating set with the least number of vertices is called a minimum dominating set. Find a minimum dominating set for the given graph.**

The minimum dominating set for the graph is \(\left\{ {c,d} \right\}\).

**A minimum dominating set is one that isn't a legitimate subset of some other dominating set in a graph. The domatic number of a graph can be calculated with minimal dominant sets.**

As each of the other vertices, *a*, *b*, *e*, and *f,* is next to at least one of the cords,*c* and *d*,\(\left\{ {c,d} \right\}\) is the smallest dominating set, implying that there is no other smaller dominating set.

Thus, the minimum dominating set for the given graph is \(\left\{ {c,d} \right\}\).

94% of StudySmarter users get better grades.

Sign up for free