Game domination number
type: Item
instance of: scholarly article
title: Game domination number
zbMATH Open document ID: 1010.05049
DOI: 10.1016/S0012-365X(00)00358-7
author: Noga Alon
author: József Balogh
author: Béla Bollobás
author: Tamás T. Szabó
published in: Discrete Mathematics
publication date: 2002-12-02T00:00:00Z
review text: 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.
reviewed by: G. Gutin
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 91A43
zbMATH DE Number: 1838908
zbMATH Keywords: dominating set
zbMATH Keywords: digraph
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1838908