Domination Game: A proof of the $3/5$-Conjecture for Graphs with Minimum Degree at Least Two
Authors:
- Michael A. HenningMHMichael A. Henning
- William B. KinnersleyWKWilliam B. Kinnersley
- 1 January 2016
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 30 (1) , 20-35
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 $\gamma_g (G)$. In this paper, we prove that $\gamma_g(G) \le 2n/3$ for every $n$-vertex isolate-free graph $G$. When $G$ has minimum degree at least $2$, we prove the stronger bound $\gamma_g(G) \le 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 $\ell$ vertices of degree 1, then $\gamma_g(G) \le 3n/5 + \left \lceil \ell/2 \right \rceil + 1$; in the course of establishing this result, we answer a question of Brešar e...
Keywords
This publication has 18 references indexed in Scilit:
- Domination game on forestsDiscrete Mathematics, 2015
- Domination game: Effect of edge- and vertex-removalDiscrete Mathematics, 2014
- Game matching number of graphsDiscrete Applied Mathematics, 2013
- Domination game: Extremal families of graphs for-conjecturesDiscrete Applied Mathematics, 2013
- Domination game played on trees and spanning subgraphsDiscrete Mathematics, 2013
- On-line Ramsey Theory for Bounded Degree GraphsThe Electronic Journal of Combinatorics, 2011
- Domination Game and an Imagination StrategySIAM Journal on Discrete Mathematics, 2010
- On-line Ramsey TheoryThe Electronic Journal of Combinatorics, 2004
- A bound for the game chromatic number of graphsDiscrete Mathematics, 1999
- Mathematical GamesScientific American, 1981