Game domination number
The dominating set of a digraph \(D\) is a set \(S\) of vertices such that for every \(v\not\in S\) there exists \(u\in S\) with \(uv\in A(D)\). The domination number of \(D\) is the cardinality of the smallest dominating set. The game domination number of an undirected graph \(G\) is the domination number of the digraph \(D\) obtained as a result of the following game, where both players play optimally. Two players orient the edges of \(G\) alternatively and the first player (second player) tries to minimize (maximize) the domination number of \(D\). The authors determine the game domination number for several families of graphs and prove general inequalities.
scientific article; zbMATH DE number 1838908