Question

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.

Short answer

The minimum dominating set for the graph is \(\left\{ {c,\;e,\;g,\;l} \right\}\).

Step-by-step solution

Concept/Significance of a minimum dominant set

In a given graph, the minimum dominating set is the dominating set with the least size. The dominance number of a graph is the size of the minimum dominating set.

A minimumdominating set is usually a minimal dominating set, but the vice-versa is not true.

Determination of the minimum dominant set of the graph

With only three vertices, it is impossible to cover the complete network because, in a basic graph, the dominant set of vertices is a set of vertices where every other vertex is adjacent to at least one vertex of this set.

Furthermore, in this scenario, a set with three vertices and dominating at the same moment does not exist. It is possible to check any permutation of three vertices. As a result, the dominant set's minimum number of vertices must be four, and\(\left\{ {c,\;e,\;g,\;l} \right\}\)is the minimum dominant set as it covers it.

Thus, the minimumdominating set forthe given graph is \(\left\{ {c,\;e,\;g,\;l} \right\}\).