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