8.4. The Independent Domination Number
A set S of vertices or edges in a graph G is said to be maximal with respect to a property P if S has property P but no proper superset of S has property P.
A set S of vertices or edges in a graph G is said to be minimal with respect to a property P if S has property P but no proper subset of S has property P.
Example: , where
, there are two maximal independent
sets of vertices: the partite sets of
.
A maximal independent set of vertices of maximum cardinality in a graph G is called a maximum independent set of vertices.
The number of vertices in a maximum independent set has
been called the independence number of G, and has been denoted by .
The minimum cardinality of a maximal independent set of
vertices of G is the lower independence number .
Example: for , where
,
and
.
Every maximal independent set of vertices in a graph is a dominating set of G.
A set S of vertices in a graph G is called an independent dominating set if S is both independent and dominating set of G.
The independent domination number of G is the minimum cardinality among
all independent dominating sets of G.
?
Theorem 8.9. ( Berge, 1973): A set S of vertices in a graph is an independent dominating set iff S is maximal independent.
Proof.
We have seen already that every maximal independent set of vertices is a dominating set.
Conversely, suppose that S is an independent dominating set.
Then S is independent and every vertex not in S is adjacent to a vertex of S, so S is maximal independent.
Theorem 8.10. Every maximal independent set of vertices in a graph is a minimal ominating set.
Proof.
Let S be a maximal independent set of vertices in a graph G.
By Theorem 8.9, S is a dominating set.
Since S is independent, certainly every vertex of S is adjacent to no vertex of S.
Thus, every vertex of S satisfies the second property of Theorem 11.1.
So, by Theorem 8.1, S is a minimal dominating set.
Can equality hold? Is there any graph G with ?
Examples:
- For
, for every positive integer t.
- For
. let H be the graph obtained from
by adding a pendant edge to each vertex of the partite set of cardinality s. Then
.
- For the queen´s graph G, we have
.
May the difference between the indepent domination number and domination number of a graph be arbitrary large?
The double star T containing two vertices of
degree , where
and
.
For some special classes of graphs, Bollobás and
Cockayne determined an upper bound for in terms of
.
Theorem 8.11. If G is a -free graph, where
, then
.
Proof.
Let S be a minimum domination set of vertices of G
and let be a maximal independent set of vertices of S in G.
Thus, and
.
Now, let T denote
the set of all vertices in that are
adjac-ent in G to no vertex of
and let
be a maximal
independent set of vertices in T.
Then, is an
independent set of vertices of G.
Since every vertex of is adjacent to
some vertex of
and every vertex of
is adjacent to
some vertex of
, it follows that
is a maximal
independent set of vertices.
Thus, by Theorem 8.9,
is an
independent dominating set.
Observe that every
vertex of is adjacent to
at most
vertices of
. (If this were
not the case, then some vertex v of
is adjacent to
at least k vertices of
, and also at least one vertex of
, which contradicts the hypothesis that G
contains no induced subgraph isomorphic to
.)
Also, observe that every
vertex of is adjacent to
some vertex of
.
Therefore
| T′ | ≤ (k - 1) | S - S′ | = (k - 1) (| S |- | S′ | ) = (k - 1) (γ(G) - | S′ |).
Consequently
