Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4646942 | Discrete Mathematics | 2015 | 9 Pages |
In the domination game studied here, Dominator and Staller alternately choose a vertex of a graph GG and take it into a set DD. The number of vertices dominated by the set DD must increase with each move and the game ends when DD becomes a dominating set of GG. Dominator aims to minimize while Staller aims to maximize the number of turns (or equivalently, the size of the dominating set DD obtained at the end). Assuming that Dominator starts and both players play optimally, the number of turns is the game domination number γg(G)γg(G) of GG.Kinnersley, West, and Zamani proved that γg(G)≤7n/11γg(G)≤7n/11 for every isolate-free nn-vertex forest GG, and they conjectured that the sharp upper bound is only 3n/53n/5. Here, we prove the 3/5-conjecture for forests in which no two leaves are at distance 4 apart. Further, we establish an upper bound γg(G)≤5n/8γg(G)≤5n/8 for every nn-vertex isolate-free forest GG.