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