8.2. Minimal Dominating Set.

A minimal dominating set in a graph G is a dominating set that contains no dominating set as a proper subset.

A minimal dominating set of minimum cardinality is a minimum dominating set and consists of  vertices.

Theorem 8.1. A dominating set S of a graph G is a minimal dominating set of G iff every vertex v in S satisfies at least one of the following two properties:

  • there exists a vertex w in  such that
  • v is adjacent to no vertex of S.

Proof.

If each vertex v in S has at least one of the properties  then  is not a dominating set of G.

Consequently, S is a minimal dominating set of G.

Assume that S is a minimal dominating set of G.

Then for each , the set  is not a dominating set of G.

Hence there is a vertex w in  that is adjacent to no vertex of .

  • If then v is adjacent to no vertex of S.
  • Suppose then that .

Since S is a dominating set and , the vertex w is adjacent to at least one vertex of S. However, w is adjacent to no vertex of . Consequently, .

From he above theorem the following conclusion can be stated:

Conclusion. A dominating set S of a graph G is a minimal dominating set of G iff every vertex v in S either v dominates some vertex of  that no other vertex of S dominates, or no other vertex of S dominates v.

Theorem 8.2.  If S is a minimal dominating set of a graph G without isolated vertices, then  is a dominating set of G.

Proof.

Let . Then v has at least one of the two properties of the Theorem 8.1.

  • Suppose first that there exists a vertex w in such that . Hence v is adjacent to some vertex in .
  • Suppose next that v is adjacent to no vertex in S. Then v is an isolated vertex of the subgraph .

Since v is not isolated in G, the vertex v is adjacent to some vertex of . Thus  is a dominating set of G.