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 .