## Abstract

In the domination game on a graph G, the players Dominator and Staller alternately select vertices of G. Each vertex chosen must strictly increase the number of vertices dominated. This process eventually produces a dominating set of G; Dominator aims to minimize the size of this set, while Staller aims to maximize it. The size of the dominating set produced under optimal play is the game domination number of G, denoted by γ_{g}(G). In this paper, we prove that γ_{g}(G) ≤ 2n/3 for every n-vertex isolate-free graph G. When G has minimum degree at least 2, we prove the stronger bound γ_{g}(G) ≤ 3n/5; this resolves a special case of a conjecture due to Kinnersley, West, and Zamani [SIAM J. Discrete Math., 27 (2013), pp. 2090-2107]. Finally, we prove that if G is an n-vertex isolate-free graph with l vertices of degree 1, then γ_{g}(G) ≤ 3n/5 + [l/2] + 1; in the course of establishing this result, we answer a question of Brešar et al. [Discrete Math., 330 (2014), pp. 1-10].

Original language | English |
---|---|

Pages (from-to) | 20-35 |

Number of pages | 16 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 30 |

Issue number | 1 |

DOIs | |

Publication status | Published - 2016 |

## Keywords

- Domination
- Domination game
- Game domination number

## ASJC Scopus subject areas

- General Mathematics