8.3. Bounds on the Domination Number.

Using the above theorem we have an upper bound for  in terms of the order of G.

Corollary 8.3. If G is a graph of order n without isolated vertices, then .

Proof.

Let S be a minimal dominating set of G.

By Theorem 8.2,  is a dominating set of G. Thus

.

Without proving we give some further upper bounds:

  • If  and G is not one of seven exceptional graphs then .
  • If  then .

Theorem 8.4. Let G be a graph of order n with . Then

Theorem 8.5. (Bollobás and Cockayne, 1984): Every graph G without isolated vertices contains a minimum dominating set S such that for every vertex v of S, there exists a vertex w of  such that .

Proof.

Among all minimum dominating sets of G, let S be one such that  has maximum size.

Suppose, to the contrary, that S contains a vertex v that does not have the desired property. Then - by Theorem 11.1 - v is an isolated vertex in .

Moreover, every vertex of  that is adjacent to v is adjacent to some other vertex of S as well.

Since G contains no isolated vertices, v is adjacent to a vertex w in .

Therefore,  is a minimum dominating set of G whose induced subgraph contains at least one edge incident with w and hence has a greater size than .

This produces a contradiction.

Bound for the domination number of a graph can be given in terms of the order and the maximum degree of the graph:

Theorem 8.6. If G is a graph of order n, then

Proof.

We prove first the lower bound.

Let S be a minimum dominating set of G. Then

,

implying that .  Therefore, , and so

Now, we establish the upper bound: Let v be a vertex of G with .

Then  is a dominating set of cardinality .

So, .

Corollary 8.7. If G is a graph of order n, then , where  is the vertex connectivity.

Proof.

The statement follows immediately from the inequality .

Theorem 8.8.  If G is a graph without isolated vertices, then

Proof.

Since every vertex cover of a graph without isolated vertices is a dominating set, as is every maximal independent set of vertices, so  and .

Let X be an edge cover of cardinality . Then every vertex of G is incident with at least one edge in X.

Let S be a set of vertices, obtained by selecting an incident vertex with each edge in X.

Then S is a dominating set of vertices and .

Let M be a maximum matching in G. We construct a set S of vertices consisting of one vertex incident with an edge of M for each edge of M.

Let .

Then, u and v cannot be adjacent to distinct M-unsaturated vertices x and y, respectively; otherwise  is an M-augmenting path in G, contradicting Theorem 4.1.

If u is adjacent to an M-unsaturated vertex, place u in S; otherwise place v in S. This is done for each edge in M. Thus, S is a dominating set of G, and .