pith. sign in

arxiv: 1404.1382 · v1 · pith:7NVHH6ATnew · submitted 2014-04-04 · 🧮 math.CO

Domination game on forests

classification 🧮 math.CO
keywords gamenumberdominationdominatorgammaaimsbounddominating
0
0 comments X
read the original abstract

In the domination game studied here, Dominator and Staller alternately choose a vertex of a graph $G$ and take it into a set $D$. The number of vertices dominated by the set $D$ must increase in each single turn and the game ends when $D$ becomes a dominating set of $G$. Dominator aims to minimize whilst Staller aims to maximize the number of turns (or equivalently, the size of the dominating set $D$ obtained at the end). Assuming that Dominator starts and both players play optimally, the number of turns is called the game domination number $\gamma_g(G)$ of $G$. Kinnersley, West and Zamani verified that $\gamma_g(G) \le 7n/11$ holds for every isolate-free $n$-vertex forest $G$ and they conjectured that the sharp upper bound is only $3n/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 $\gamma_g(G) \le 5n/8$, which is valid for every isolate-free forest $G$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.