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 et al. [Discrete Math., 330 (2014), pp. 1--10].

In the domination game on a graph $G$, two players called Dominator and Staller alternately select vertices of $G$. Each vertex chosen must strictly increase the number of vertices dominated; the game ends when the chosen set becomes a dominating set of $G$. Dominator aims to minimize the size of the resulting dominating set, while Staller aims to maximize it. When both players play optimally, the size of the dominating set produced is the game domination number of $G$, denoted by $\gamma_g(G)$ when Dominator plays first and by $\gamma_g^\prime(G)$ when Staller plays first. We prove that $\gamma_g(G) \le 7n/11$ when $G$ is an isolate-free $n$-vertex forest and that $\gamma_g(G) \le \left\lceil7n/10\right\rceil$ for any isolate-free $n$-vertex graph. In both cases we conjecture that $\gamma_g(G) \le 3n/5$ and prove it when $G$ is a forest of nontrivial caterpillars. We also resolve conjectures of Brešar, Klavžar, and Rall by showing that always $\gamma_g^\prime(G)\le\gamma_g(G)+1$, that for $k\ge2$ there are graphs $G$ satisfying $\gamma_g(G) = 2k$ and $\gamma_g^\prime(G) = 2k-1$, and that $\gamma_g^\prime(G) \ge \gamma_g(G)$ when $G$ is a forest. Our results follow from fundamental lemmas about the domination game that simplify its analysis and may be useful in future research.

A Roman dominating function of a graph G is a labeling $f\colon\,V(G)\to\{0,1,2\}$ such that every vertex with label 0 has a neighbor with label 2. The Roman domination number $\gamma_R(G)$ of G is the minimum of $\sum_{v\in V(G)}f(v)$ over such functions. Let G be a connected n-vertex graph. We prove that $\gamma_R(G)\leq4n/5$, and we characterize the graphs achieving equality. We obtain sharp upper and lower bounds for $\gamma_R(G)+\gamma_R(\overline{G})$ and $\gamma_R(G)\gamma_R(\overline{G})$, improving known results for domination number. We prove that $\gamma_R(G)\leq8n/11$ when $\delta(G)\geq2$ and $n\geq9$, and this is sharp.