Abstract
The game domination number of a (simple, undirected) graph is defined by the following game. Two players,
\documentclass{article}\usepackage{amssymb}\usepackage{amsbsy}\usepackage[mathscr]{euscript}\footskip=0pc\pagestyle{empty}\begin{document}${\mathcal{A}}$\end{document} and
\documentclass{article}\usepackage{amssymb}\usepackage{amsbsy}\usepackage[mathscr]{euscript}\footskip=0pc\pagestyle{empty}\begin{document}${\mathcal{D}}$\end{document}, orient the edges of the graph alternately until all edges are oriented. Player
\documentclass{article}\usepackage{amssymb}\usepackage{amsbsy}\usepackage[mathscr]{euscript}\footskip=0pc\pagestyle{empty}\begin{document}${\mathcal{D}}$\end{document} starts the game, and his goal is to decrease the domination number of the resulting digraph, while
\documentclass{article}\usepackage{amssymb}\usepackage{amsbsy}\usepackage[mathscr]{euscript}\footskip=0pc\pagestyle{empty}\begin{document}${\mathcal{A}}$\end{document} is trying to increase it. The game domination number of the graph G, denoted by ฮณ~g~(G), is the domination number of the directed graph resulting from this game. This is well defined if we suppose that both players follow their optimal strategies. Alon et al. (Discrete Math 256 (2002), 23โ33) conjectured that, if both G and \documentclass{article}\usepackage{amssymb}\usepackage{amsbsy}\usepackage[mathscr]{euscript}\footskip=0pc\pagestyle{empty}\begin{document}$\overline{G}$\end{document} are connected graphs with n vertices, then \documentclass{article}\usepackage{amssymb}\usepackage{amsbsy}\usepackage[mathscr]{euscript}\footskip=0pc\pagestyle{empty}\begin{document}$\gamma_{g}(G)+\gamma_{g}(\overline{G})\le\frac{2}{3}{n}+{3}$\end{document}. In this paper we prove that this conjecture is true for nโฉพ41. ยฉ 2009 Wiley Periodicals, Inc. J Graph Theory 64: 323โ329, 2010