DOMINATION GAME CRITICAL GRAPHS

作者：Bujtas Csilla; Klavzar Sandi; Kosmrlj Gasper

来源：Discussiones Mathematicae - Graph Theory, 2015, 35(4): 781-796.

DOI：10.7151/dmgt.1839

• domination number
• domination game
• domination game critical graphs
• powers of cycles
• trees

The domination game is played on a graph G by two players who alternately take turns by choosing a vertex such that in each turn at least one previously undominated vertex is dominated. The game is over when each vertex becomes dominated. One of the players, namely Dominator, wants to finish the game as soon as possible, while the other one wants to delay the end. The number of turns when Dominator starts the game on G and both players play optimally is the graph invariant gamma(g)(G), named the game domination number. Here we study the gamma(g)-critical graphs which are critical with respect to vertex predomination. Besides proving some general properties, we characterize gamma(g)-critical graphs with gamma(g) = 2 and with gamma(g) = 3, moreover for each n we identify the (infinite) class of all gamma(g)-critical ones among the nth powers C-N(n) of cycles. Along the way we determine gamma(g)(C-N(n)) for all n and N. Results of a computer search for gamma(g)-critical trees are presented and several problems and research directions are also listed.

• 出版日期2015