8.1. Definitions

A vertex v in a graph G is said to dominate itself and each of its neighbours. We say with other words that v dominates the vertices of its closed neighborhood. .

A set S of vertices of G is a dominating set of G if every vertices of G is dominated by at least one vertex of S.

Equivalently: a set S of vertices of G is a dominating set if every vertex in  is adjacent to at least one vertex in S.

The minimum cardinality among the dominating sets of G is called the domination number of G and denoted by .

A dominating set of cardinality  is referred to as a minimum dominating set.

As an example we show an interesting problem (Jaenisch,1862):  Determine the minimum number of queens that can be placed on the chessboard such that every square is either occupied by one of the queens in a single move.

Two queens on a chessboard are attacking if the square occupied by one of the queens can be reached by the other queen in a single move. Otherwise, they are nonattacking queens.

In the queen graph of a chessboard the squares are the vertices and two vertices are adjacent  in G if each square can be reached by a queen on the other square by a single move.

The minimum number of nonattacking queens that dominate all the squares of a chessboard is the minimum cardinality of an indepen-dent dominating set in G.