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.